結果

問題 No.1212 Second Path
ユーザー 👑 hos.lyric
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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) {
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0