Submit Info #21128

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

ケース詳細
Name Status Time Memory
dense_00 AC 881 ms 35.89 MiB
dense_01 AC 648 ms 31.33 MiB
dense_02 AC 586 ms 36.09 MiB
example_00 AC 119 ms 18.60 MiB
max_random_00 AC 955 ms 255.59 MiB
max_random_01 AC 1166 ms 373.32 MiB
max_random_02 AC 1276 ms 389.54 MiB
random_00 AC 772 ms 222.20 MiB
random_01 AC 556 ms 140.12 MiB
random_02 AC 247 ms 75.57 MiB
random_03 AC 239 ms 53.33 MiB
random_04 AC 634 ms 218.25 MiB
small_00 AC 61 ms 5.25 MiB
small_01 AC 64 ms 5.00 MiB
small_02 AC 68 ms 5.02 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; struct Node { public int[] child; public int parent; public int l; public int r; public int sz; public T val; public T sum; public byte flags; } static int nodeCount = 1; static Node[] nodeList = new Node[16384]; [MethodImpl(MethodImplOptions.AggressiveInlining)] static int NewNode() { 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(); nodeList[nodeCount].child = new int[2]; return nodeCount++; } [MethodImpl(MethodImplOptions.AggressiveInlining)] static int NewNode(int l, int r) { var id = NewNode(); nodeList[id].l = l; nodeList[id].r = r; nodeList[id].sz = 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].parent != 0) t = nodeList[t].parent; 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 = nodeList[s].child[0]; nodeList[s].child[0] = nodeList[t].parent = 0; return (t, UpdateNode(s)); } [MethodImpl(MethodImplOptions.AggressiveInlining)] (int, int) Split2(int s) { if (s == 0) return (0, 0); Splay(s); var t = nodeList[s].child[0]; var u = nodeList[s].child[1]; nodeList[s].child[0] = nodeList[s].child[1] = nodeList[t].parent = nodeList[u].parent = 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 (nodeList[s].child[1] != 0) s = nodeList[s].child[1]; Splay(s); nodeList[s].child[1] = t; if (t != 0) nodeList[t].parent = s; return UpdateNode(s); } [MethodImpl(MethodImplOptions.AggressiveInlining)] int UpdateNode(int t) { if (t == 0) return 0; var sum = ei; var leftChild = nodeList[t].child[0]; var rightChild = nodeList[t].child[1]; if (leftChild != 0) sum = f(sum, nodeList[leftChild].sum); if (nodeList[t].l == nodeList[t].r) sum = f(sum, nodeList[t].val); if (rightChild != 0) sum = f(sum, nodeList[rightChild].sum); nodeList[t].sum = sum; nodeList[t].sz = nodeList[leftChild].sz + (nodeList[t].l == nodeList[t].r ? 1 : 0) + nodeList[rightChild].sz; 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 = nodeList[t].parent; var y = nodeList[x].parent; if ((nodeList[x].child[1 - b] = nodeList[t].child[b]) != 0) nodeList[nodeList[t].child[b]].parent = x; nodeList[t].child[b] = x; nodeList[x].parent = t; UpdateNode(x); UpdateNode(t); if ((nodeList[t].parent = y) != 0) { if (nodeList[y].child[0] == x) nodeList[y].child[0] = t; if (nodeList[y].child[1] == x) nodeList[y].child[1] = t; UpdateNode(y); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] void Splay(int t) { if (t == 0) return; Push(t); while (nodeList[t].parent != 0) { var q = nodeList[t].parent; var r = nodeList[q].parent; if (r == 0) { Push(q); Push(t); Rot(t, nodeList[q].child[0] == t ? 1 : 0); } else { Push(r); Push(q); Push(t); var b = nodeList[r].child[0] == q ? 1 : 0; if (nodeList[q].child[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 = GetNode(s, s); Splay(t); return nodeList[t].sz; } [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 => { if (nodeList[node].l < nodeList[node].r && (nodeList[node].flags & 8) != 0) { Splay(node); nodeList[node].flags &= 7; g(nodeList[node].l, nodeList[node].r, idx); return; } if ((nodeList[nodeList[node].child[0]].flags & 4) != 0) dfs(nodeList[node].child[0]); else dfs(nodeList[node].child[1]); }; 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(nodeList[node].l, idx); } if ((nodeList[nodeList[node].child[0]].flags & 1) != 0) return dfs(nodeList[node].child[0]); else return dfs(nodeList[node].child[1]); }; 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()); } }