Submit Info #21125

Problem Lang User Status Time Memory
Dynamic Graph Vertex Add Component Sum csharp (anonymous) WA 1802 ms 389.59 MiB

ケース詳細
Name Status Time Memory
dense_00 WA 1802 ms 32.82 MiB
dense_01 RE 457 ms 18.12 MiB
dense_02 WA 1249 ms 32.59 MiB
example_00 AC 87 ms 11.96 MiB
max_random_00 AC 975 ms 324.88 MiB
max_random_01 AC 982 ms 324.92 MiB
max_random_02 AC 1125 ms 389.59 MiB
random_00 AC 870 ms 255.45 MiB
random_01 AC 605 ms 170.68 MiB
random_02 AC 238 ms 66.95 MiB
random_03 AC 220 ms 52.14 MiB
random_04 AC 563 ms 247.95 MiB
small_00 AC 59 ms 5.15 MiB
small_01 AC 71 ms 5.05 MiB
small_02 AC 69 ms 4.96 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 ulong NEIGHBOR_MASK = 2097151; struct Node { public ulong neighbor; public ulong lrsz; public T val; public T sum; public byte flags; } static Node[] nodeList = new Node[16384]; static int nodeCount = 1; [MethodImpl(MethodImplOptions.AggressiveInlining)] static EulerTourTree() { nodeList[0] = new Node(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] static int NewNode() { if (nodeCount == (int)NEIGHBOR_MASK) throw new Exception(); if (nodeCount == nodeList.Length) { var tmp = new Node[nodeCount << 1]; for (var i = 0; i < nodeList.Length; i++) tmp[i] = nodeList[i]; nodeList = tmp; } nodeList[nodeCount] = new Node(); return nodeCount++; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static int NewNode(int l, int r) { var id = NewNode(); nodeList[id].lrsz |= (ulong)(((ulong)l << 42) | ((ulong)r << 21) | (uint)(l == r ? 1 : 0)); if (l < r) nodeList[id].flags = 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); nodeList[nodePoint].val = nodeList[nodePoint].sum = 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 ((nodeList[t].neighbor >> 42) != 0) t = (int)((nodeList[t].neighbor >> 42) & 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)(nodeList[s].neighbor & NEIGHBOR_MASK); nodeList[t].neighbor &= ~(NEIGHBOR_MASK << 42); nodeList[s].neighbor &= ~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)(nodeList[s].neighbor & NEIGHBOR_MASK); var u = (int)((nodeList[s].neighbor >> 21) & NEIGHBOR_MASK); nodeList[s].neighbor &= NEIGHBOR_MASK << 42; nodeList[t].neighbor &= ~(NEIGHBOR_MASK << 42); nodeList[u].neighbor &= ~(NEIGHBOR_MASK << 42); 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 (((nodeList[s].neighbor >> 21) & NEIGHBOR_MASK) != 0) s = (int)(((nodeList[s].neighbor >> 21) & NEIGHBOR_MASK)); Splay(s); nodeList[s].neighbor &= ~(NEIGHBOR_MASK << 21); nodeList[s].neighbor |= (ulong)t << 21; if (t != 0) { nodeList[t].neighbor &= ~(NEIGHBOR_MASK << 42); nodeList[t].neighbor |= (ulong)s << 42; } return UpdateNode(s); } [MethodImpl(MethodImplOptions.AggressiveInlining)] int UpdateNode(int t) { if (t == 0) return 0; var sum = ei; var leftChild = nodeList[t].neighbor & NEIGHBOR_MASK; var rightChild = (nodeList[t].neighbor >> 21) & NEIGHBOR_MASK; var same = (uint)(((nodeList[t].lrsz >> 42) == ((nodeList[t].lrsz >> 21) & NEIGHBOR_MASK)) ? 1 : 0); if (leftChild != 0) sum = f(sum, nodeList[leftChild].sum); if (same == 1) sum = f(sum, nodeList[t].val); if (rightChild != 0) sum = f(sum, nodeList[rightChild].sum); nodeList[t].sum = sum; nodeList[t].lrsz &= ~NEIGHBOR_MASK; nodeList[t].lrsz |= (ulong)((nodeList[leftChild].lrsz & NEIGHBOR_MASK) + same + (nodeList[leftChild].lrsz & NEIGHBOR_MASK)); var flag = nodeList[leftChild].flags | (nodeList[t].flags >> 1) | nodeList[rightChild].flags; if ((flag & 1) != 0) nodeList[t].flags |= 1; else nodeList[t].flags &= 14; if ((flag & 4) != 0) nodeList[t].flags |= 4; else nodeList[t].flags &= 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)(nodeList[t].neighbor >> 42); var y = (int)(nodeList[x].neighbor >> 42); var xmaskShift = (1 - b) * 21; var tchild = (nodeList[t].neighbor >> (b * 21) & NEIGHBOR_MASK); nodeList[x].neighbor &= ~(NEIGHBOR_MASK << xmaskShift); nodeList[x].neighbor |= tchild << xmaskShift; if (tchild != 0) { nodeList[tchild].neighbor &= ~(NEIGHBOR_MASK << 42); nodeList[tchild].neighbor |= (ulong)x << 42; } var tmaskshift = b * 21; nodeList[t].neighbor &= ~(NEIGHBOR_MASK << tmaskshift); nodeList[t].neighbor |= (ulong)x << tmaskshift; nodeList[x].neighbor &= ~(NEIGHBOR_MASK << 42); nodeList[x].neighbor |= (ulong)t << 42; UpdateNode(x); UpdateNode(t); nodeList[t].neighbor &= ~(NEIGHBOR_MASK << 42); nodeList[t].neighbor |= (ulong)y << 42; if (y != 0) { if ((nodeList[y].neighbor & NEIGHBOR_MASK) == (ulong)x) { nodeList[y].neighbor &= ~NEIGHBOR_MASK; nodeList[y].neighbor |= (ulong)((uint)t); } if (((nodeList[y].neighbor >> 21) & NEIGHBOR_MASK) == (ulong)x) { nodeList[y].neighbor &= ~(NEIGHBOR_MASK << 21); nodeList[y].neighbor |= (ulong)t << 21; } UpdateNode(y); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Splay(int t) { if (t == 0) return; Push(t); while ((nodeList[t].neighbor & (NEIGHBOR_MASK << 42)) != 0) { var q = (int)(nodeList[t].neighbor >> 42); var r = (int)(nodeList[q].neighbor >> 42); if (r == 0) { Push(q); Push(t); Rot(t, (nodeList[q].neighbor & NEIGHBOR_MASK) == (ulong)t ? 1 : 0); } else { Push(r); Push(q); Push(t); var b = (nodeList[r].neighbor & NEIGHBOR_MASK) == (ulong)q ? 1 : 0; if (((nodeList[q].neighbor >> ((1 - b) * 21)) & NEIGHBOR_MASK) == (ulong)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 (int)(nodeList[t].lrsz & NEIGHBOR_MASK); } [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 nodeList[t].val; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Update(int s, T x) { var t = GetNode(s, s); Splay(t); nodeList[t].val = 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 => { var nodel = nodeList[node].lrsz >> 42; var noder = (nodeList[node].lrsz >> 21) & NEIGHBOR_MASK; if (nodel < noder && (nodeList[node].flags & 8) != 0) { Splay(node); nodeList[node].flags &= 7; g((int)nodel, (int)noder, idx); return; } var leftChild = (int)(nodeList[node].neighbor & NEIGHBOR_MASK); if ((nodeList[leftChild].flags & 4) != 0) dfs(leftChild); else dfs((int)((nodeList[node].neighbor >> 21) & NEIGHBOR_MASK)); }; while ((nodeList[t].flags & 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 ((nodeList[node].flags & 2) != 0) { Splay(node); return f((int)(nodeList[node].lrsz >> 42), idx); } var leftChild = (int)(nodeList[node].neighbor & NEIGHBOR_MASK); if ((nodeList[leftChild].flags & 1) != 0) return dfs(leftChild); else return dfs((int)((nodeList[node].neighbor >> 21) & NEIGHBOR_MASK)); }; while ((nodeList[t].flags & 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) nodeList[t].flags |= 2; else nodeList[t].flags &= 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 = nodeList[t].sum; Link(p, v); return res; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Query(int s) { var t = GetNode(s, s); Splay(t); return nodeList[t].sum; } } } 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()); } }