Submit Info #21195

Problem Lang User Status Time Memory
Dynamic Graph Vertex Add Component Sum csharp (anonymous) AC 791 ms 164.14 MiB

ケース詳細
Name Status Time Memory
dense_00 AC 791 ms 29.84 MiB
dense_01 AC 619 ms 27.65 MiB
dense_02 AC 595 ms 28.52 MiB
example_00 AC 155 ms 19.58 MiB
max_random_00 AC 411 ms 103.13 MiB
max_random_01 AC 447 ms 151.63 MiB
max_random_02 AC 518 ms 164.14 MiB
random_00 AC 382 ms 94.12 MiB
random_01 AC 263 ms 62.39 MiB
random_02 AC 146 ms 28.29 MiB
random_03 AC 147 ms 28.32 MiB
random_04 AC 218 ms 72.64 MiB
small_00 AC 67 ms 5.21 MiB
small_01 AC 63 ms 5.20 MiB
small_02 AC 66 ms 5.20 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_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()); } class LIB_DynamicConnectivity<T> { Func<T, T, T> f; T ei; int n; int dep = 1; List<EulerTourTree> ett; List<Dictionary<int, 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<Dictionary<int, HashSet<int>>>(); ett.Add(new EulerTourTree(this.n, ei, f)); edges.Add(new Dictionary<int, HashSet<int>>()); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Link(long s, long t) { if (s == t) return; var ints = (int)s; var intt = (int)t; if (ett[0].Link(ints, intt)) return; HashSet<int> sEdges, tEdges; if (!edges[0].TryGetValue(ints, out sEdges)) edges[0][ints] = sEdges = new HashSet<int>(); if (!edges[0].TryGetValue(intt, out tEdges)) edges[0][intt] = tEdges = new HashSet<int>(); sEdges.Add(intt); tEdges.Add(ints); if (sEdges.Count == 1) ett[0].EdgeConnectedUpdate(ints, true); if (tEdges.Count == 1) ett[0].EdgeConnectedUpdate(intt, true); } [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; var ints = (int)s; var intt = (int)t; for (var i = 0; i < dep; i++) { var edgesi = edges[i]; HashSet<int> sEdges, tEdges; if (!edgesi.TryGetValue(ints, out sEdges)) edgesi[ints] = sEdges = new HashSet<int>(); if (!edgesi.TryGetValue(intt, out tEdges)) edgesi[intt] = tEdges = new HashSet<int>(); sEdges.Remove(intt); tEdges.Remove(ints); if (sEdges.Count == 0) ett[i].EdgeConnectedUpdate(ints, false); if (tEdges.Count == 0) ett[i].EdgeConnectedUpdate(intt, 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 Dictionary<int, HashSet<int>>()); } 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 edgesidx = edges[idx]; HashSet<int> xEdges; if (!edgesidx.TryGetValue(x, out xEdges)) edgesidx[x] = xEdges = new HashSet<int>(); foreach (var y in xEdges.ToArray()) { HashSet<int> yEdges; if (!edgesidx.TryGetValue(y, out yEdges)) edgesidx[y] = yEdges = new HashSet<int>(); xEdges.Remove(y); 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)) { HashSet<int> nextXEdges, nextYEdges; var edgesidx1 = edges[idx + 1]; if (!edgesidx1.TryGetValue(x, out nextXEdges)) edgesidx1[x] = nextXEdges = new HashSet<int>(); if (!edgesidx1.TryGetValue(y, out nextYEdges)) edgesidx1[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), int> ptr; int startNodeIndex; static int[] nodeChild = new int[32768]; static int[] nodeParent = new int[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(int l, int r) { if (nodeCount == nodeParent.Length) { { var tmp = new int[nodeCount << 2]; var cnt = nodeCount << 1; for (var i = 0; i < cnt; i++) tmp[i] = nodeChild[i]; nodeChild = tmp; } { var tmp = new int[nodeCount << 1]; for (var i = 0; i < nodeCount; i++) tmp[i] = nodeParent[i]; nodeParent = 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; } } var id = nodeCount++; 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), int>(); this.f = f; this.ei = ei; this.startNodeIndex = nodeCount; for (var i = 0; i < n; i++) { var nodePoint = NewNode(i, i); nodeVal[nodePoint] = nodeSum[nodePoint] = ei; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] int Root(int t) { while (nodeParent[t] != 0) t = nodeParent[t]; 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) { Splay(s); var t = nodeChild[s << 1]; nodeChild[s << 1] = nodeParent[t] = 0; return (t, UpdateNode(s)); } [MethodImpl(MethodImplOptions.AggressiveInlining)] (int, int) Split2(int s) { if (s == 0) return (0, 0); Splay(s); var t = nodeChild[s << 1]; var u = nodeChild[(s << 1) | 1]; nodeChild[s << 1] = nodeParent[t] = nodeChild[(s << 1) | 1] = nodeParent[u] = 0; 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 (nodeChild[(s << 1) | 1] != 0) s = nodeChild[(s << 1) | 1]; Splay(s); nodeChild[(s << 1) | 1] = t; if (t != 0) nodeParent[t] = s; return UpdateNode(s); } [MethodImpl(MethodImplOptions.AggressiveInlining)] int UpdateNode(int t) { if (t == 0) return 0; var sum = ei; var leftChild = nodeChild[t << 1]; var rightChild = nodeChild[(t << 1) | 1]; 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 = nodeParent[t]; var y = nodeParent[x]; if ((nodeChild[(x << 1) | (1 - b)] = nodeChild[(t << 1) | b]) != 0) nodeParent[nodeChild[(t << 1) | b]] = x; nodeChild[(t << 1) | b] = x; nodeParent[x] = t; UpdateNode(x); UpdateNode(t); if ((nodeParent[t] = y) != 0) { if (nodeChild[y << 1] == x) nodeChild[y << 1] = t; if (nodeChild[(y << 1) | 1] == x) nodeChild[(y << 1) | 1] = t; UpdateNode(y); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Splay(int t) { if (t == 0) return; Push(t); while (nodeParent[t] != 0) { var q = nodeParent[t]; if (nodeParent[q] == 0) { Push(q); Push(t); Rot(t, nodeChild[q << 1] == t ? 1 : 0); } else { var r = nodeParent[q]; Push(r); Push(q); Push(t); var b = nodeChild[r << 1] == q ? 1 : 0; if (nodeChild[(q << 1) | (1 - b)] == 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 = startNodeIndex + s; Splay(t); return nodeSz[t]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool IsSame(int s, int t) => IsSameNode(startNodeIndex + s, startNodeIndex + t); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Get(int s) { var t = startNodeIndex + s; Splay(t); return nodeVal[t]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Update(int s, T x) { var t = startNodeIndex + 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 = startNodeIndex + s; Splay(t); while ((nodeFlags[t] & 4) != 0) { var node = t; while (true) { if (nodeL[node] < nodeR[node] && (nodeFlags[node] & 8) != 0) { Splay(node); nodeFlags[node] &= 7; g(nodeL[node], nodeR[node], idx); break; } if ((nodeFlags[nodeChild[node << 1]] & 4) != 0) node = nodeChild[node << 1]; else node = nodeChild[(node << 1) | 1]; } Splay(t); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool TryReconnect(int s, Func<int, int, bool> f, int idx) { var t = startNodeIndex + s; Splay(t); while ((nodeFlags[t] & 1) != 0) { var node = t; while (true) { if ((nodeFlags[node] & 2) != 0) { Splay(node); if (f(nodeL[node], idx)) return true; break; } if ((nodeFlags[nodeChild[node << 1]] & 1) != 0) node = nodeChild[node << 1]; else node = nodeChild[(node << 1) | 1]; } Splay(t); } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void EdgeConnectedUpdate(int s, bool b) { var t = startNodeIndex + 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 (l > r) { var t = l; l = r; r = t; } if (IsSameNode(startNodeIndex + l, startNodeIndex + r)) return false; var lv = ReRoot(startNodeIndex + l); var rv = ReRoot(startNodeIndex + r); int lrnode; if (!ptr.TryGetValue((l, r), out lrnode)) { ptr[(l, r)] = lrnode = NewNode(l, r); NewNode(r, l); } nodeParent[lv] = nodeParent[rv] = lrnode; nodeChild[lrnode << 1] = lv; nodeChild[(lrnode << 1) | 1] = rv; UpdateNode(lrnode); Merge(lrnode, lrnode + 1); return true; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool Cut(int l, int r) { if (l > r) { var t = l; l = r; r = t; } if (!ptr.ContainsKey((l, r))) return false; var p = ptr[(l, r)]; var s = Split(p, p + 1); Merge(s.Item1, s.Item3); ptr.Remove((l, r)); return true; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(int p, int v) { Cut(p, v); var t = startNodeIndex + v; Splay(t); var res = nodeSum[t]; Link(p, v); return res; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(int s) { var t = startNodeIndex + s; Splay(t); return nodeSum[t]; } } } }