結果
| 問題 | No.529 帰省ラッシュ |
| ユーザー |
 eitaho
|
| 提出日時 | 2017-06-11 19:03:21 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,077 ms / 4,500 ms |
| コード長 | 13,829 bytes |
| コンパイル時間 | 3,662 ms |
| コンパイル使用メモリ | 114,332 KB |
| 実行使用メモリ | 128,040 KB |
| 最終ジャッジ日時 | 2023-08-22 10:57:56 |
| 合計ジャッジ時間 | 17,147 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 79 ms
24,892 KB |
| testcase_01 | AC | 80 ms
24,872 KB |
| testcase_02 | AC | 80 ms
22,780 KB |
| testcase_03 | AC | 78 ms
22,772 KB |
| testcase_04 | AC | 92 ms
25,104 KB |
| testcase_05 | AC | 91 ms
24,916 KB |
| testcase_06 | AC | 91 ms
26,940 KB |
| testcase_07 | AC | 91 ms
26,916 KB |
| testcase_08 | AC | 821 ms
78,200 KB |
| testcase_09 | AC | 779 ms
84,652 KB |
| testcase_10 | AC | 1,007 ms
115,040 KB |
| testcase_11 | AC | 988 ms
114,200 KB |
| testcase_12 | AC | 643 ms
68,876 KB |
| testcase_13 | AC | 896 ms
114,012 KB |
| testcase_14 | AC | 772 ms
71,524 KB |
| testcase_15 | AC | 1,077 ms
127,912 KB |
| testcase_16 | AC | 1,059 ms
128,040 KB |
| testcase_17 | AC | 1,058 ms
118,648 KB |
| testcase_18 | AC | 931 ms
118,332 KB |
| testcase_19 | AC | 925 ms
118,460 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;
public class Program
{
public void Solve()
{
int N = Reader.Int(), M = Reader.Int(), NQ = Reader.Int();
var E = Reader.IntTable(M);
var Q = Reader.IntTable(NQ);
var comp = new TwoEdgeConnectedComponent(N, E, 1);
var hld = new HLDecomposition(comp.Count, comp.ComponentEdges);
var seg = hld.Path.Select(p => new MaxHeapSegmentTree(p.Count)).ToArray();
var ans = new List<int>();
foreach (var q in Q)
if (q[0] == 1)
{
int v = comp.VtoComponentId(q[1] - 1), val = q[2];
seg[hld.Y[v]].Add(hld.X[v], val);
}
else
{
int a = comp.VtoComponentId(q[1] - 1), b = comp.VtoComponentId(q[2] - 1);
int maxVal = -1, pathId = 0, index = 0;
Action<int, int, int> Pop = (p, L, R) =>
{
int v, i;
v = seg[p].Max(out i, L, R);
if (v > maxVal) { pathId = p; maxVal = v; index = i; }
};
hld.Query(a, b, Pop);
ans.Add(maxVal);
if (maxVal >= 0) seg[pathId].PopAt(index);
}
if (ans.Count > 0) Console.WriteLine(string.Join("\n", ans));
}
}
public class Component
{
public List<int> Vertexes;
public int[] Edges;
public Component(List<int> vs) { Vertexes = vs; }
}
public class TwoEdgeConnectedComponent
{
int N, id;
List<int>[] E;
int[] VtoCompId, order;
bool[] inS;
Stack<int> S = new Stack<int>(), roots = new Stack<int>();
List<Component> Components = new List<Component>();
HashSet<long> BridgesSet = new HashSet<long>();
public List<int[]> Bridges = new List<int[]>();
public int[][] ComponentEdges;
public int Count { get { return Components.Count; } }
public Component this[int i] { get { return Components[i]; } }
public bool IsBridge(int a, int b) { return BridgesSet.Contains(ToKey(a, b)); }
public int VtoComponentId(int v) { return VtoCompId[v]; }
public bool SameComponent(int a, int b) { return VtoCompId[a] == VtoCompId[b]; }
public TwoEdgeConnectedComponent(int N) { Init(N); }
public TwoEdgeConnectedComponent(int N, int[][] E, int origin = 0)
{
Init(N);
Array.ForEach(E, e => AddEdge(e[0] - origin, e[1] - origin));
Decompose();
}
void Init(int N)
{
this.N = N;
VtoCompId = new int[N];
order = new int[N];
inS = new bool[N];
E = new List<int>[N];
for (int i = 0; i < N; i++) E[i] = new List<int>();
}
public void AddEdge(int a, int b)
{
E[a].Add(b);
E[b].Add(a);
}
public void Decompose()
{
for (int i = 0; i < N; i++) if (order[i] == 0) DFS(i);
CheckEdges();
}
void CheckEdges()
{
Bridges.Sort((a, b) => a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
var es = new List<int[]>();
for (int compId = 0; compId < Count; compId++)
{
var comp = Components[compId];
var set = new HashSet<int>();
foreach (int a in comp.Vertexes)
foreach (int b in E[a])
if (VtoCompId[a] != VtoCompId[b])
set.Add(VtoCompId[b]);
comp.Edges = set.ToArray();
Array.Sort(comp.Edges);
foreach (int b in comp.Edges)
if (compId < b)
es.Add(new[] { compId, b });
}
ComponentEdges = es.ToArray();
}
void DFS(int start)
{
var stack = new Stack<int>();
stack.Push(-1); stack.Push(start);
for (; stack.Count > 0; )
{
int v = stack.Pop(), prev = stack.Pop();
if (v < 0)
{
v = ~v;
foreach (int next in E[v])
if (next != prev && inS[next])
while (order[roots.Peek()] > order[next]) roots.Pop();
if (roots.Peek() != v) continue;
if (prev != -1) AddBridge(prev, v);
AddComponent(prev, v);
}
else
{
if (order[v] != 0) continue;
stack.Push(prev); stack.Push(~v);
order[v] = ++id;
roots.Push(v);
S.Push(v);
inS[v] = true;
foreach (int next in E[v])
if (order[next] == 0) { stack.Push(v); stack.Push(next); }
}
}
}
void AddBridge(int a, int b)
{
BridgesSet.Add(ToKey(a, b));
Bridges.Add(new[] { Math.Min(a, b), Math.Max(a, b) });
}
void AddComponent(int prev, int root)
{
int compId = Components.Count;
var vs = new List<int>();
for (; ; )
{
int v = S.Pop();
inS[v] = false;
VtoCompId[v] = compId;
vs.Add(v);
if (v == root) break;
}
vs.Sort();
Components.Add(new Component(vs));
roots.Pop();
}
long ToKey(long a, long b) { return a < b ? a * N + b : b * N + a; }
}
public class HLDecomposition
{
int N;
List<int>[] E;
public int[] Y, X, Size, Parent, Up, UnderL, UnderR;
public List<List<int>> Path = new List<List<int>>();
List<int> PathDepth = new List<int>();
// F(pathId, L, R)
public void Query(int a, int b, Action<int, int, int> F)
{
for (int at = Y[a], L = 0, R, na = a, nb = b; a != -1; a = na, b = nb)
{
if (Y[a] == Y[b]) { at = Y[a]; L = Math.Min(X[a], X[b]); R = Math.Max(X[a], X[b]); na = -1; }
else if (PathDepth[Y[a]] >= PathDepth[Y[b]]) { at = Y[a]; L = 0; R = X[a]; na = Up[a]; }
else { at = Y[b]; L = 0; R = X[b]; nb = Up[b]; }
F(at, L, R + 1);
}
}
public HLDecomposition(int N) { Init(N); }
public HLDecomposition(int N, int[][] E, int origin = 0)
{
Init(N);
Array.ForEach(E, e => AddEdge(e[0] - origin, e[1] - origin));
Build();
}
void Init(int N)
{
this.N = N;
Y = new int[N]; X = new int[N];
Size = new int[N]; Parent = new int[N]; Up = new int[N];
UnderL = new int[N]; UnderR = new int[N];
E = new List<int>[N];
for (int i = 0; i < N; i++) E[i] = new List<int>();
}
public void AddEdge(int a, int b)
{
E[a].Add(b);
E[b].Add(a);
}
public void Build()
{
CountNodes();
CompressPath();
}
void CountNodes()
{
var stack = new Stack<int>();
var nodes = new int[N];
int ni = N - 1;
stack.Push(0);
while (stack.Count > 0)
{
int a = stack.Pop();
for (int ei = 0; ei < E[a].Count; ei++)
{
int b = E[a][ei];
if (b == Parent[a]) { E[a].RemoveAt(ei); ei--; }
else { Parent[b] = a; stack.Push(b); }
}
nodes[ni--] = a;
}
foreach (int a in nodes)
{
Size[a] = 1;
var e = E[a];
for (int i = 0; i < e.Count; i++)
{
int b = e[i];
Size[a] += Size[b];
if (Size[b] > Size[e[0]]) { int t = e[0]; e[0] = b; e[i] = t; }
}
}
}
void CompressPath()
{
var stack = new Stack<int>();
stack.Push(0);
while (stack.Count > 0)
{
int a = stack.Pop();
if (a < 0) { UnderR[~a] = Path.Count; continue; }
if (X[a] == 0)
{
Path.Add(new List<int>());
PathDepth.Add(a == 0 ? 0 : PathDepth[Y[Parent[a]]] + 1);
}
int pathId = Y[a] = Path.Count - 1;
Path[pathId].Add(a);
Up[a] = Parent[Path[pathId][0]];
UnderL[a] = Path.Count;
stack.Push(~a);
if (E[a].Count == 0) continue;
for (int i = E[a].Count - 1; i > 0; i--)
stack.Push(E[a][i]);
X[E[a][0]] = X[a] + 1;
stack.Push(E[a][0]);
}
}
public int LCA(int a, int b)
{
if (Y[a] == Y[b]) return (X[a] < X[b]) ? a : b;
if (PathDepth[Y[a]] >= PathDepth[Y[b]])
return LCA(Parent[Path[Y[a]][0]], b);
return LCA(a, Parent[Path[Y[b]][0]]);
}
public int Dist(int a, int b)
{
if (Y[a] == Y[b]) return Math.Abs(X[a] - X[b]);
if (PathDepth[Y[a]] >= PathDepth[Y[b]])
return X[a] + 1 + Dist(Parent[Path[Y[a]][0]], b);
return X[b] + 1 + Dist(a, Parent[Path[Y[b]][0]]);
}
}
public class MaxHeapSegmentTree
{
static readonly long[] Q = new long[100];
public readonly int N;
readonly int[] Val;
readonly int[] Who;
readonly HeapMax[] heap;
public MaxHeapSegmentTree(int n)
{
for (N = 2; N < n; ) N *= 2;
heap = new HeapMax[N];
Val = new int[N * 2];
Who = new int[N * 2];
for (int i = 0; i < N; i++)
{
heap[i] = new HeapMax(2);
heap[i].Push(int.MinValue);
Who[N + i] = i;
}
for (int i = 0; i < Val.Length; i++) Val[i] = int.MinValue;
}
public void Add(int index, int val)
{
heap[index].Push(val);
int i = index + N;
Val[i] = heap[index].Peek();
for (i >>= 1; i > 0; i >>= 1)
if (Val[i << 1] >= Val[i << 1 | 1]) { Val[i] = Val[i << 1]; Who[i] = Who[i << 1]; }
else { Val[i] = Val[i << 1 | 1]; Who[i] = Who[i << 1 | 1]; }
}
public int Max(int L = 0, int R = int.MaxValue) { int d; return Max(out d, L, R); }
public int Max(out int index, int L = 0, int R = int.MaxValue)
{
index = -1;
int res = int.MinValue;
Q[0] = 1L << 32;
for (int s = 0, t = 1, len = N, first = 1; s != t; ++s)
{
int i = (int)(Q[s] >> 32), a = (int)Q[s];
if (s == first) { len >>= 1; first = t; }
if (Val[i] < res || Val[i] == res && Who[i] > index) continue;
if (a >= L && a + len <= R) { res = Val[i]; index = Who[i]; continue; }
int mid = a + (len >> 1);
if (L < mid) Q[t++] = ((long)(i << 1) << 32) + a;
if (R > mid) Q[t++] = ((long)(i << 1 | 1) << 32) + mid;
}
return res;
}
public int Pop(int L = 0, int R = int.MaxValue)
{
int index;
int maxVal = Max(out index, L, R);
return PopAt(index);
}
public int PopAt(int index)
{
int val = heap[index].Pop();
int i = index + N;
Val[i] = heap[index].Peek();
for (i >>= 1; i > 0; i >>= 1)
if (Val[i << 1] >= Val[i << 1 | 1]) { Val[i] = Val[i << 1]; Who[i] = Who[i << 1]; }
else { Val[i] = Val[i << 1 | 1]; Who[i] = Who[i << 1 | 1]; }
return val;
}
}
public class HeapMax
{
int[] A;
public HeapMax(int size = 1000) { A = new int[size]; }
public int Count { get; private set; }
public int Peek() { return A[1]; }
public void Push(int val)
{
int i = ++Count;
if (i == A.Length) Array.Resize(ref A, A.Length * 2);
for (; i > 1 && val > A[i >> 1]; i >>= 1) A[i] = A[i >> 1];
A[i] = val;
}
public int Pop()
{
int res = A[1], val = A[Count--];
if (Count == 0) return res;
int i = 1;
for (int L = i << 1; L <= Count; L = i << 1)
{
if (L + 1 <= Count && A[L + 1] > A[L]) L++;
if (A[L] > val) { A[i] = A[L]; i = L; }
else break;
}
A[i] = val;
return res;
}
}
class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
static TextReader reader = Console.In;
static readonly char[] separator = { ' ' };
static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
static string[] A = new string[0];
static int i;
static void Init() { Dispose(); A = new string[0]; }
public static void Set(TextReader r) { Init(); reader = r; }
public static void Set(string file) { Init(); reader = new StreamReader(file); }
public static bool HasNext() { return CheckNext(); }
public static string String() { return Next(); }
public static int Int() { return int.Parse(Next()); }
public static long Long() { return long.Parse(Next()); }
public static double Double() { return double.Parse(Next()); }
public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
public static int[] IntArray(int N) { return Range(N, Int); }
public static int[][] IntTable(int H) { return Range(H, IntLine); }
public static string[] StringArray(int N) { return Range(N, Next); }
public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
public static string Line() { return reader.ReadLine().Trim(); }
public static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
public static void Dispose() { reader.Dispose(); }
static string[] Split(string s) { return s.Split(separator, op); }
static string Next() { CheckNext(); return A[i++]; }
static bool CheckNext()
{
if (i < A.Length) return true;
string line = reader.ReadLine();
if (line == null) return false;
if (line == "") return CheckNext();
A = Split(line);
i = 0;
return true;
}
}