Submit Info #21114

Problem Lang User Status Time Memory
Dynamic Graph Vertex Add Component Sum csharp (anonymous) TLE 10000 ms 309.69 MiB

ケース詳細
Name Status Time Memory
dense_00 AC 887 ms 24.95 MiB
dense_01 AC 670 ms 23.20 MiB
dense_02 AC 604 ms 23.79 MiB
example_00 AC 106 ms 11.98 MiB
max_random_00 AC 774 ms 204.82 MiB
max_random_01 TLE 10000 ms 295.63 MiB
max_random_02 TLE 10000 ms 309.69 MiB
random_00 AC 694 ms 177.87 MiB
random_01 AC 484 ms 120.70 MiB
random_02 AC 211 ms 62.70 MiB
random_03 AC 218 ms 41.71 MiB
random_04 AC 457 ms 175.51 MiB
small_00 AC 67 ms 5.31 MiB
small_01 AC 61 ms 5.16 MiB
small_02 AC 60 ms 5.17 MiB

using System; using System.Collections.Generic; using System.IO; using System.Linq; using static System.Math; using System.Text; using System.Threading; using System.Globalization; using System.Runtime.CompilerServices; using Library; namespace Program { public static class ProblemA { static bool SAIKI = false; static public int numberOfRandomCases = 0; static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker) { } static public void Solve() { var N = NN; var Q = NN; var aList = NNList(N); var graph = new LIB_DynamicConnectivity<long>(N, 0, (x, y) => x + y); for (var i = 0; i < N; i++) { graph[i] = aList[i]; } for (var i = 0; i < Q; i++) { var t = NN; if (t == 0) { var u = NN; var v = NN; graph.Link(u, v); } else if (t == 1) { var u = NN; var v = NN; graph.Cut(u, v); } else if (t == 2) { var v = NN; var x = NN; graph[v] += x; } else { var v = NN; Console.WriteLine(graph.Query(v)); } } } class Printer : StreamWriter { public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; } public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; } } static LIB_FastIO fastio = new LIB_FastIODebug(); static public void Main(string[] args) { if (args.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); } static long NN => fastio.Long(); static double ND => fastio.Double(); static string NS => fastio.Scan(); static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray(); static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray(); static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray(); static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred); static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n); static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c); static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e); static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector); static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase); static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase); static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x); static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } } static IEnumerator<uint> _xsi = _xsc(); static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } } } } namespace Library { class LIB_DynamicConnectivity<T> { Func<T, T, T> f; T ei; int n; int dep = 1; List<EulerTourTree> ett; List<HashSet<int>[]> edges; [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_DynamicConnectivity(long n, T ei, Func<T, T, T> f) { this.n = (int)n; this.f = f; this.ei = ei; ett = new List<EulerTourTree>(); edges = new List<HashSet<int>[]>(); ett.Add(new EulerTourTree(this.n, ei, f)); edges.Add(new HashSet<int>[n]); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Link(long s, long t) { if (s == t) return false; if (ett[0].Link((int)s, (int)t)) return true; var sEdges = edges[0][s]; var tEdges = edges[0][t]; if (sEdges == null) edges[0][s] = sEdges = new HashSet<int>(); if (tEdges == null) edges[0][t] = tEdges = new HashSet<int>(); sEdges.Add((int)t); tEdges.Add((int)s); if (sEdges.Count == 1) ett[0].EdgeConnectedUpdate((int)s, true); if (tEdges.Count == 1) ett[0].EdgeConnectedUpdate((int)t, true); return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool IsSame(long s, long t) => ett[0].IsSame((int)s, (int)t); [MethodImpl(MethodImplOptions.AggressiveInlining)] public long Size(long s) => ett[0].Size((int)s); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(long s) => ett[0].Query((int)s); [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Cut(long s, long t) { if (s == t) return false; for (var i = 0; i < dep; i++) { var sEdges = edges[i][s]; var tEdges = edges[i][t]; if (sEdges == null) edges[i][s] = sEdges = new HashSet<int>(); if (tEdges == null) edges[i][t] = tEdges = new HashSet<int>(); sEdges.Remove((int)t); tEdges.Remove((int)s); if (sEdges.Count == 0) ett[i].EdgeConnectedUpdate((int)s, false); if (tEdges.Count == 0) ett[i].EdgeConnectedUpdate((int)t, false); } for (var i = dep - 1; i >= 0; i--) { if (ett[i].Cut((int)s, (int)t)) { if (dep - 1 == i) { ++dep; ett.Add(new EulerTourTree(n, ei, f)); edges.Add(new HashSet<int>[n]); } return !TryReconnect((int)s, (int)t, i); } } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] bool TryReconnect(int s, int t, int k) { for (var i = 0; i < k; i++) ett[i].Cut(s, t); for (var i = k; i >= 0; i--) { var etti = ett[i]; if (etti.Size(s) > etti.Size(t)) { var temp = s; s = t; t = temp; } etti.EdgeUpdate(s, (ss, tt, idx) => ett[idx + 1].Link(ss, tt), i); if (etti.TryReconnect(s, (x, idx) => { var xEdges = edges[idx][x]; if (xEdges == null) edges[idx][x] = xEdges = new HashSet<int>(); foreach (var y in xEdges.ToArray()) { xEdges.Remove(y); var yEdges = edges[idx][y]; if (yEdges == null) edges[idx][y] = yEdges = new HashSet<int>(); yEdges.Remove(x); if (xEdges.Count == 0) ett[idx].EdgeConnectedUpdate(x, false); if (yEdges.Count == 0) ett[idx].EdgeConnectedUpdate(y, false); if (ett[idx].IsSame(x, y)) { var nextXEdges = edges[idx + 1][x]; var nextYEdges = edges[idx + 1][y]; if (nextXEdges == null) edges[idx + 1][x] = nextXEdges = new HashSet<int>(); if (nextYEdges == null) edges[idx + 1][y] = nextYEdges = new HashSet<int>(); nextXEdges.Add(y); nextYEdges.Add(x); if (nextXEdges.Count == 1) ett[idx + 1].EdgeConnectedUpdate(x, true); if (nextYEdges.Count == 1) ett[idx + 1].EdgeConnectedUpdate(y, true); } else { for (var j = 0; j <= idx; j++) ett[j].Link(x, y); return true; } } return false; }, i)) return true; } return false; } public T this[long index] { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { return ett[0].Get((int)index); } [MethodImpl(MethodImplOptions.AggressiveInlining)] set { ett[0].Update((int)index, value); } } class EulerTourTree { Func<T, T, T> f; T ei; Dictionary<int, int>[] ptr; const long NEIGHBOR_MASK = 1048575; static long[] nodeNeighbor = new long[16384]; static int[] nodeL = new int[16384]; static int[] nodeR = new int[16384]; static int[] nodeSz = new int[16384]; static T[] nodeVal = new T[16384]; static T[] nodeSum = new T[16384]; static byte[] nodeFlags = new byte[16384]; static int nodeCount = 1; [MethodImpl(MethodImplOptions.AggressiveInlining)] static int NewNode() { if (nodeCount == nodeNeighbor.Length) { { var tmp = new long[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeNeighbor[i]; nodeNeighbor = tmp; } { var tmp = new int[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeL[i]; nodeL = tmp; } { var tmp = new int[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeR[i]; nodeR = tmp; } { var tmp = new int[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeSz[i]; nodeSz = tmp; } { var tmp = new T[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeVal[i]; nodeVal = tmp; } { var tmp = new T[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeSum[i]; nodeSum = tmp; } { var tmp = new byte[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeFlags[i]; nodeFlags = tmp; } } return nodeCount++; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static int NewNode(int l, int r) { var id = NewNode(); nodeL[id] = l; nodeR[id] = r; nodeSz[id] = l == r ? 1 : 0; if (l < r) nodeFlags[id] = 12; return id; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public EulerTourTree(int n, T ei, Func<T, T, T> f) { this.ptr = new Dictionary<int, int>[n]; this.f = f; this.ei = ei; for (var i = 0; i < n; i++) { ptr[i] = new Dictionary<int, int>(); var nodePoint = ptr[i][i] = NewNode(i, i); nodeVal[nodePoint] = nodeSum[nodePoint] = ei; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] int GetNode(int l, int r) { if (!ptr[l].ContainsKey(r)) ptr[l][r] = NewNode(l, r); return ptr[l][r]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] int Root(int t) { while ((nodeNeighbor[t] >> 40) != 0) t = (int)((nodeNeighbor[t] >> 40) & NEIGHBOR_MASK); return t; } [MethodImpl(MethodImplOptions.AggressiveInlining)] bool IsSameNode(int s, int t) { Splay(s); Splay(t); return Root(s) == Root(t); } [MethodImpl(MethodImplOptions.AggressiveInlining)] int ReRoot(int t) { if (t == 0) return 0; var s = Split(t); return Merge(s.Item2, s.Item1); } [MethodImpl(MethodImplOptions.AggressiveInlining)] (int, int) Split(int s) { if (s == 0) return (0, 0); Splay(s); var t = (int)(nodeNeighbor[s] & NEIGHBOR_MASK); nodeNeighbor[t] &= ~(NEIGHBOR_MASK << 40); nodeNeighbor[s] &= ~NEIGHBOR_MASK; return (t, UpdateNode(s)); } [MethodImpl(MethodImplOptions.AggressiveInlining)] (int, int) Split2(int s) { if (s == 0) return (0, 0); Splay(s); var t = (int)(nodeNeighbor[s] & NEIGHBOR_MASK); var u = (int)((nodeNeighbor[s] >> 20) & NEIGHBOR_MASK); nodeNeighbor[s] &= NEIGHBOR_MASK << 40; nodeNeighbor[t] &= ~(NEIGHBOR_MASK << 40); nodeNeighbor[u] &= ~(NEIGHBOR_MASK << 40); return (t, u); } [MethodImpl(MethodImplOptions.AggressiveInlining)] (int, int, int) Split(int s, int t) { var u = Split2(s); if (IsSameNode(u.Item1, t)) { var r = Split2(t); return (r.Item1, r.Item2, u.Item2); } else { var r = Split2(t); return (u.Item1, r.Item1, r.Item2); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] int Merge(int s, int t) { if (s == 0) return t; if (t == 0) return s; while (((nodeNeighbor[s] >> 20) & NEIGHBOR_MASK) != 0) s = (int)(((nodeNeighbor[s] >> 20) & NEIGHBOR_MASK)); Splay(s); nodeNeighbor[s] &= ~(NEIGHBOR_MASK << 20); nodeNeighbor[s] |= (long)t << 20; if (t != 0) { nodeNeighbor[t] &= ~(NEIGHBOR_MASK << 40); nodeNeighbor[t] |= (long)s << 40; } return UpdateNode(s); } [MethodImpl(MethodImplOptions.AggressiveInlining)] int UpdateNode(int t) { if (t == 0) return 0; var sum = ei; var leftChild = nodeNeighbor[t] & NEIGHBOR_MASK; var rightChild = (nodeNeighbor[t] >> 20) & NEIGHBOR_MASK; if (leftChild != 0) sum = f(sum, nodeSum[leftChild]); if (nodeL[t] == nodeR[t]) sum = f(sum, nodeVal[t]); if (rightChild != 0) sum = f(sum, nodeSum[rightChild]); nodeSum[t] = sum; nodeSz[t] = nodeSz[leftChild] + (nodeL[t] == nodeR[t] ? 1 : 0) + nodeSz[rightChild]; var flag = nodeFlags[leftChild] | (nodeFlags[t] >> 1) | nodeFlags[rightChild]; if ((flag & 1) != 0) nodeFlags[t] |= 1; else nodeFlags[t] &= 14; if ((flag & 4) != 0) nodeFlags[t] |= 4; else nodeFlags[t] &= 11; return t; } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Push(int t) { // todo } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Rot(int t, int b) { if (t == 0) return; var x = (int)(nodeNeighbor[t] >> 40); var y = (int)(nodeNeighbor[x] >> 40); var xmaskShift = (1 - b) * 20; var tchild = (nodeNeighbor[t] >> (b * 20) & NEIGHBOR_MASK); nodeNeighbor[x] &= ~(NEIGHBOR_MASK << xmaskShift); nodeNeighbor[x] |= tchild << xmaskShift; if (tchild != 0) { nodeNeighbor[tchild] &= ~(NEIGHBOR_MASK << 40); nodeNeighbor[tchild] |= (long)x << 40; } var tmaskshift = b * 20; nodeNeighbor[t] &= ~(NEIGHBOR_MASK << tmaskshift); nodeNeighbor[t] |= (long)x << tmaskshift; nodeNeighbor[x] &= ~(NEIGHBOR_MASK << 40); nodeNeighbor[x] |= (long)t << 40; UpdateNode(x); UpdateNode(t); nodeNeighbor[t] &= ~(NEIGHBOR_MASK << 40); nodeNeighbor[t] |= (long)y << 40; if (y != 0) { if ((nodeNeighbor[y] & NEIGHBOR_MASK) == x) { nodeNeighbor[y] &= ~NEIGHBOR_MASK; nodeNeighbor[y] |= (long)t; } if (((nodeNeighbor[y] >> 20) & NEIGHBOR_MASK) == x) { nodeNeighbor[y] &= ~(NEIGHBOR_MASK << 20); nodeNeighbor[y] |= (long)t << 20; } UpdateNode(y); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Splay(int t) { if (t == 0) return; Push(t); while ((nodeNeighbor[t] & (NEIGHBOR_MASK << 40)) != 0) { var q = (int)(nodeNeighbor[t] >> 40); var r = (int)(nodeNeighbor[q] >> 40); if (r == 0) { Push(q); Push(t); Rot(t, (nodeNeighbor[q] & NEIGHBOR_MASK) == t ? 1 : 0); } else { Push(r); Push(q); Push(t); var b = (nodeNeighbor[r] & NEIGHBOR_MASK) == q ? 1 : 0; if (((nodeNeighbor[q] >> ((1 - b) * 20)) & NEIGHBOR_MASK) == t) { Rot(q, b); Rot(t, b); } else { Rot(t, 1 - b); Rot(t, b); } } } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public int Size(int s) { var t = GetNode(s, s); Splay(t); return nodeSz[t]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool IsSame(int s, int t) => IsSameNode(GetNode(s, s), GetNode(t, t)); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Get(int s) { var t = GetNode(s, s); Splay(t); return nodeVal[t]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Update(int s, T x) { var t = GetNode(s, s); Splay(t); nodeVal[t] = x; UpdateNode(t); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void EdgeUpdate(int s, Action<int, int, int> g, int idx) { var t = GetNode(s, s); Splay(t); Action<int> dfs = null; dfs = node => { if (nodeL[node] < nodeR[node] && (nodeFlags[node] & 8) != 0) { Splay(node); nodeFlags[node] &= 7; g(nodeL[node], nodeR[node], idx); return; } var leftChild = (int)(nodeNeighbor[node] & NEIGHBOR_MASK); if ((nodeFlags[leftChild] & 4) != 0) dfs(leftChild); else dfs((int)((nodeNeighbor[node] >> 20) & NEIGHBOR_MASK)); }; while ((nodeFlags[t] & 4) != 0) { dfs(t); Splay(t); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool TryReconnect(int s, Func<int, int, bool> f, int idx) { var t = GetNode(s, s); Splay(t); Func<int, bool> dfs = null; dfs = node => { if ((nodeFlags[node] & 2) != 0) { Splay(node); return f(nodeL[node], idx); } var leftChild = (int)(nodeNeighbor[node] & NEIGHBOR_MASK); if ((nodeFlags[leftChild] & 1) != 0) return dfs(leftChild); else return dfs((int)((nodeNeighbor[node] >> 20) & NEIGHBOR_MASK)); }; while ((nodeFlags[t] & 1) != 0) { if (dfs(t)) return true; Splay(t); } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void EdgeConnectedUpdate(int s, bool b) { var t = GetNode(s, s); Splay(t); if (b) nodeFlags[t] |= 2; else nodeFlags[t] &= 13; UpdateNode(t); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Link(int l, int r) { if (IsSame(l, r)) return false; Merge(Merge(Merge(ReRoot(GetNode(l, l)), GetNode(l, r)), ReRoot(GetNode(r, r))), GetNode(r, l)); return true; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Cut(int l, int r) { if (!ptr[l].ContainsKey(r)) return false; var s = Split(GetNode(l, r), GetNode(r, l)); Merge(s.Item1, s.Item3); var p = ptr[l][r]; var q = ptr[r][l]; ptr[l].Remove(r); ptr[r].Remove(l); return true; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(int p, int v) { Cut(p, v); var t = GetNode(v, v); Splay(t); var res = nodeSum[t]; Link(p, v); return res; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(int s) { var t = GetNode(s, s); Splay(t); return nodeSum[t]; } } } class LIB_FastIO { [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIO() { str = Console.OpenStandardInput(); } readonly Stream str; readonly byte[] buf = new byte[1024]; int len, ptr; public bool isEof = false; public bool IsEndOfStream { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { return isEof; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] byte read() { if (isEof) throw new EndOfStreamException(); if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] char Char() { byte b = 0; do b = read(); while (b < 33 || 126 < b); return (char)b; } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public long Long() { long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } } class LIB_FastIODebug : LIB_FastIO { Queue<string> param = new Queue<string>(); [MethodImpl(MethodImplOptions.AggressiveInlining)] string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public LIB_FastIODebug() { } [MethodImpl(MethodImplOptions.AggressiveInlining)] public override string Scan() => NextString(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override long Long() => long.Parse(NextString()); [MethodImpl(MethodImplOptions.AggressiveInlining)] public override double Double() => double.Parse(NextString()); } }