結果
問題 | No.812 Change of Class |
ユーザー |
|
提出日時 | 2020-01-12 14:58:15 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 337 ms / 4,000 ms |
コード長 | 2,640 bytes |
コンパイル時間 | 1,833 ms |
コンパイル使用メモリ | 151,320 KB |
実行使用メモリ | 16,804 KB |
最終ジャッジ日時 | 2024-06-22 04:06:03 |
合計ジャッジ時間 | 12,368 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
ソースコード
// URL: https://yukicoder.me/problems/no/812import std.algorithm, std.container, std.math, std.range, std.typecons, std.string;version(unittest) {} elsevoid main(){int n, m; io.getV(n, m);auto g = Graph(n);foreach (_; 0..m) {int p, q; io.getV(p, q); --p; --q;g.addEdgeB(p, q);}int q; io.getV(q);foreach (_; 0..q) {int a; io.getV(a); --a;auto qu = DList!(g.Node)(a);auto md = 0, d = new int[](n), c = 0;d[] = -1; d[a] = 0;while (!qu.empty) {auto u = qu.front; qu.removeFront();++c;foreach (v; g[u]) {if (d[v] == -1) {d[v] = d[u] + 1;md = max(md, d[v]);qu.insertBack(v);}}}auto x = 0;while (md > 1) {++x;md = (md+1) / 2;}io.put(c-1, x);}}struct Graph{alias Node = int;Node n;Node[][] g;alias g this;this(Node n) { this.n = n; g = new Node[][](n); }void addEdge(Node u, Node v) { g[u] ~= v; }void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; }}auto io = IO();struct IO{import std.algorithm, std.conv, std.format, std.meta, std.range, std.stdio, std.traits;dchar[] buf;auto sp = (new dchar[](0)).splitter;int precision = 10;string delimiter = " ";void nextLine(){stdin.readln(buf);sp = buf.splitter;}auto get(T)(ref T v){if (sp.empty) nextLine();v = sp.front.to!T;sp.popFront();}auto getV(T...)(ref T v){foreach (ref w; v) get(w);}auto getA(T)(size_t n, ref T v)if (hasAssignableElements!T){v = new T(n);foreach (ref w; v) get(w);}auto getC(T...)(size_t n, ref T v)if (allSatisfy!(hasAssignableElements, T)){foreach (ref w; v)w = new typeof(w)(n);foreach (i; 0..n)foreach (ref w; v) get(w[i]);}auto getM(T)(size_t r, size_t c, ref T v)if (hasAssignableElements!T && hasAssignableElements!(ElementType!T)){v = new T(r);foreach (ref w; v) getA(c, w);}auto rangePop(R)(ref R r){r.popFront();if (!r.empty) write(delimiter);}auto putA(T)(T v){static if (isInputRange!T && !isSomeString!T)for (auto w = v; !w.empty; rangePop(w)) putA(w.front);else if (isFloatingPoint!T)writef(format("%%.%df", precision), v);elsewrite(v);}auto put(T...)(T v){foreach (i, w; v) {putA(w);if (i < v.length-1) write(delimiter);}writeln;}auto putB(S, T)(bool c, S t, T f){if (c)put(t);elseput(f);}auto dbg(T...)(T v){stderr.writeln(v);}}