結果
問題 | No.1212 Second Path |
ユーザー |
👑 |
提出日時 | 2020-08-30 17:17:39 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 501 ms / 3,000 ms |
コード長 | 7,024 bytes |
コンパイル時間 | 1,059 ms |
コンパイル使用メモリ | 123,220 KB |
実行使用メモリ | 82,176 KB |
最終ジャッジ日時 | 2024-06-22 08:48:08 |
合計ジャッジ時間 | 17,263 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;(unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }int N;int[] A, B;long[] C;int[][] G;int[] par, dep;long[] dist;void dfs(int u, int p, int ip) {par[u] = p;dep[u] = (p == -1) ? 0 : (dep[p] + 1);dist[u] = (p == -1) ? 0 : (dist[p] + C[ip]);foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != p) {dfs(v, u, i);}}}enum E = 17;enum INF = 10L^^18;struct Info {int last;long mn;long[2] xs;};Info mul(in Info f, in Info g) {Info h;h.last = g.last;h.mn = min(f.mn,(g.xs[0] != dist[f.last] - dist[par[f.last]]) ? g.xs[0] : g.xs[1],g.mn);h.xs = f.xs;return h;}void main() {try {for (; ; ) {N = readInt();A = new int[N - 1];B = new int[N - 1];C = new long[N - 1];foreach (i; 0 .. N - 1) {A[i] = readInt() - 1;B[i] = readInt() - 1;C[i] = readLong();}const Q = readInt();auto X = new int[Q];auto Y = new int[Q];foreach (q; 0 .. Q) {X[q] = readInt() - 1;Y[q] = readInt() - 1;}G = new int[][N];foreach (i; 0 .. N - 1) {G[A[i]] ~= i;G[B[i]] ~= i;}par = new int[N];dep = new int[N];dist = new long[N];dfs(0, -1, -1);auto dd = new Info[][](E, N);foreach (u; 0 .. N) {dd[0][u].last = u;dd[0][u].mn = INF;dd[0][u].xs[] = INF;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != par[u]) {long tmp = C[i];foreach (k; 0 .. 2) {if (dd[0][u].xs[k] > tmp) {swap(dd[0][u].xs[k], tmp);}}}}}foreach (e; 0 .. E - 1) {foreach (u; 0 .. N) {const l = dd[e][u].last;if (l == -1 || par[l] == -1) {dd[e + 1][u] = dd[e][u];} else {dd[e + 1][u] = mul(dd[e][u], dd[e][par[l]]);}}}debug {foreach (e; 0 .. E - 1) {writefln("dd[%s] = %s", e, dd[e]);}}auto mns = new long[][](N, 3);foreach (u; 0 .. N) {mns[u][] = INF;foreach (i; G[u]) {long tmp = C[i];foreach (k; 0 .. 3) {if (mns[u][k] > tmp) {swap(mns[u][k], tmp);}}}}debug {auto d = new long[][](N, N);foreach (u; 0 .. N) {d[u][] = INF;d[u][u] = 0;}foreach (i; 0 .. N - 1) {chmin(d[A[i]][B[i]], C[i]);chmin(d[B[i]][A[i]], C[i]);}foreach (w; 0 .. N) foreach (u; 0 .. N) foreach (v; 0 .. N) {chmin(d[u][v], d[u][w] + d[w][v]);}}foreach (q; 0 .. Q) {int u = X[q], v = Y[q];if (dep[u] > dep[v]) {swap(u, v);}debug {writefln("dep[%s] = %s, dep[%s] = %s", u, dep[u], v, dep[v]);}int lca;long ans = INF;Info fu, fv;fu.last = fv.last = -2;foreach_reverse (e; 0 .. E) {if (dep[u] <= dep[v] - (1 << e)) {debug {writefln("%s -> %s", v, par[dd[e][v].last]);}fv = (fv.last == -2) ? dd[e][v] : mul(fv, dd[e][v]);v = par[dd[e][v].last];}}if (u == v) {debug {writeln("u == v");writeln("fv = ", fv);}lca = u;chmin(ans, (mns[u][0] != dist[fv.last] - dist[u]) ? mns[u][0] : mns[u][1]);chmin(ans, fv.mn);chmin(ans, fv.xs[0]);} else {foreach_reverse (e; 0 .. E) {if (dep[u] - (1 << e) >= 0 && par[dd[e][u].last] != par[dd[e][v].last]) {debug {writefln("%s -> %s, %s -> %s", u, par[dd[e][u].last], v, par[dd[e][v].last]);}fu = (fu.last == -2) ? dd[e][u] : mul(fu, dd[e][u]);fv = (fv.last == -2) ? dd[e][v] : mul(fv, dd[e][v]);u = par[dd[e][u].last];v = par[dd[e][v].last];}}debug {writeln("lca = ", lca);writeln("fu = ", fu);writeln("fv = ", fv);}lca = par[u];fu = (fu.last == -2) ? dd[0][u] : mul(fu, dd[0][u]);fv = (fv.last == -2) ? dd[0][v] : mul(fv, dd[0][v]);long[2] tmps = [dist[u] - dist[lca], dist[v] - dist[lca]];if (tmps[0] > tmps[1]) {swap(tmps[0], tmps[1]);}chmin(ans, (mns[lca][0] != tmps[0]) ? mns[lca][0] : (mns[lca][1] != tmps[1]) ? mns[lca][1] : mns[lca][2]);chmin(ans, fu.mn);chmin(ans, fu.xs[0]);chmin(ans, fv.mn);chmin(ans, fv.xs[0]);}debug {writeln("lca = ", lca, ", ans = ", ans);}debug {long brt = INF;foreach (i; 0 .. N - 1) {if (d[X[q]][Y[q]] == d[X[q]][A[i]] + C[i] + d[B[i]][Y[q]] ||d[X[q]][Y[q]] == d[X[q]][B[i]] + C[i] + d[A[i]][Y[q]]) {// edge on the path} else if (d[X[q]][Y[q]] == d[X[q]][A[i]] + d[A[i]][Y[q]] ||d[X[q]][Y[q]] == d[X[q]][B[i]] + d[B[i]][Y[q]]) {chmin(brt, C[i]);}}assert(brt == ans, format("query %s %s: %s %s", X[q], Y[q], brt, ans));assert(d[X[q]][Y[q]] == dist[X[q]] + dist[Y[q]] - 2 * dist[lca]);}if (ans >= INF) {writeln(-1);} else {ans *= 2;ans += dist[X[q]] + dist[Y[q]] - 2 * dist[lca];writeln(ans);}}}} catch (EOFException e) {}}