結果
問題 | No.2337 Equidistant |
ユーザー | kakel-san |
提出日時 | 2023-06-02 22:17:45 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 3,354 ms / 4,000 ms |
コード長 | 5,031 bytes |
コンパイル時間 | 4,542 ms |
コンパイル使用メモリ | 108,672 KB |
実行使用メモリ | 217,744 KB |
最終ジャッジ日時 | 2024-06-08 23:37:32 |
合計ジャッジ時間 | 37,528 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
19,200 KB |
testcase_01 | AC | 34 ms
19,456 KB |
testcase_02 | AC | 35 ms
19,072 KB |
testcase_03 | AC | 35 ms
19,328 KB |
testcase_04 | AC | 35 ms
19,200 KB |
testcase_05 | AC | 37 ms
19,456 KB |
testcase_06 | AC | 43 ms
21,504 KB |
testcase_07 | AC | 42 ms
21,504 KB |
testcase_08 | AC | 44 ms
21,504 KB |
testcase_09 | AC | 42 ms
21,504 KB |
testcase_10 | AC | 42 ms
21,248 KB |
testcase_11 | AC | 1,412 ms
145,340 KB |
testcase_12 | AC | 1,414 ms
145,100 KB |
testcase_13 | AC | 1,451 ms
145,432 KB |
testcase_14 | AC | 1,422 ms
145,216 KB |
testcase_15 | AC | 1,429 ms
145,344 KB |
testcase_16 | AC | 1,441 ms
145,204 KB |
testcase_17 | AC | 1,429 ms
145,348 KB |
testcase_18 | AC | 1,473 ms
145,456 KB |
testcase_19 | AC | 1,499 ms
144,940 KB |
testcase_20 | AC | 1,452 ms
145,200 KB |
testcase_21 | AC | 2,266 ms
217,744 KB |
testcase_22 | AC | 1,286 ms
137,216 KB |
testcase_23 | AC | 1,283 ms
137,520 KB |
testcase_24 | AC | 3,068 ms
209,108 KB |
testcase_25 | AC | 1,421 ms
147,916 KB |
testcase_26 | AC | 3,354 ms
206,608 KB |
testcase_27 | AC | 1,420 ms
149,688 KB |
testcase_28 | AC | 1,433 ms
149,812 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray(); static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray(); public static void Main() { Solve(); } static void Solve() { var c = NList; var (n, q) = (c[0], c[1]); var map = NMap(n - 1); var query = NMap(q); var tree = new List<int>[n]; for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>(); foreach (var edge in map) { tree[edge[0]].Add(edge[1]); tree[edge[1]].Add(edge[0]); } var ccnt = new Dictionary<int, int>[n]; for (var i = 0; i < ccnt.Length; ++i) ccnt[i] = new Dictionary<int, int>(); var csum = new int[n]; var dlist = new int[n]; DFS(-1, 0, 0, tree, ccnt, csum, dlist); var dmap = DMap(n, 0, tree, dlist); var ans = new int[q]; for (var i = 0; i < q; ++i) { var s = query[i][0]; var t = query[i][1]; var l = LCA(s, t, dmap, dlist); if (l.len % 2 == 0) { if (dlist[s] == dlist[t]) { var snext = GetAncestor(s, dlist[s] - dlist[l.lca] - 1, dmap); var tnext = GetAncestor(t, dlist[t] - dlist[l.lca] - 1, dmap); ans[i] = n - ccnt[l.lca][snext] - ccnt[l.lca][tnext]; } else if (dlist[s] > dlist[t]) { var snext = GetAncestor(s, l.len / 2 - 1, dmap); var center = dmap[snext][0]; ans[i] = csum[center] - ccnt[center][snext]; } else { var tnext = GetAncestor(t, l.len / 2 - 1, dmap); var center = dmap[tnext][0]; ans[i] = csum[center] - ccnt[center][tnext]; } } } WriteLine(string.Join("\n", ans)); } static int DFS(int prev, int cur, int dep, List<int>[] tree, Dictionary<int, int>[] ccnt, int[] csum, int[] dlist) { dlist[cur] = dep; var sum = 1; foreach (var next in tree[cur]) { if (prev == next) continue; var cnt = DFS(cur, next, dep + 1, tree, ccnt, csum, dlist); ccnt[cur][next] = cnt; sum += cnt; } csum[cur] = sum; foreach (var next in tree[cur]) if (prev == next) { ccnt[cur][next] = tree.Length - sum; } return sum; } // それぞれの頂点について、2^k個前の親を計算する(ダブリング) static List<int>[] DMap(int n, int root, List<int>[] tree, int[] dep) { var dmap = new List<int>[n]; for (var i = 0; i < dmap.Length; ++i) { dmap[i] = new List<int>(); var p = 0; foreach (var parent in tree[i]) if (dep[parent] < dep[i]) { p = parent; break; } dmap[i].Add(p); } var dpos = 0; while (true) { var comp = true; for (var i = 0; i < dmap.Length; ++i) { var nv = dmap[dmap[i][dpos]][dpos]; dmap[i].Add(nv); if (nv != root) comp = false; } if (comp) break; ++dpos; } return dmap; } // ダブリングを使って頂点間の距離を高速に求める static (int lca, int len) LCA(int a, int b, List<int>[] dmap, int[] dep) { if (dep[a] < dep[b]) return LCA(b, a, dmap, dep); var res = dep[a] - dep[b]; while (dep[a] > dep[b]) { var diff = dep[a] - dep[b]; var bit = 1; var pos = 0; while (diff > 1) { bit <<= 1; diff >>= 1; ++pos; } a = dmap[a][pos]; } if (a == b) return (dmap[a][0], res); while (dmap[a][0] != dmap[b][0]) { for (var i = 1; i < dmap[a].Count; ++i) { if (dmap[a][i] == dmap[b][i]) { a = dmap[a][i - 1]; b = dmap[b][i - 1]; res += 1 << i; break; } } } return (dmap[a][0], res + 2); } static int GetAncestor(int a, int len, List<int>[] dmap) { while (len > 0) { var d = 0; while (len >= (1 << d + 1)) ++d; a = dmap[a][d]; len -= 1 << d; } return a; } }