結果
問題 | No.1212 Second Path |
ユーザー | SSRS |
提出日時 | 2020-08-30 17:02:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,089 ms / 3,000 ms |
コード長 | 4,236 bytes |
コンパイル時間 | 3,254 ms |
コンパイル使用メモリ | 237,008 KB |
実行使用メモリ | 40,580 KB |
最終ジャッジ日時 | 2024-04-27 11:16:05 |
合計ジャッジ時間 | 55,199 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 846 ms
40,068 KB |
testcase_01 | AC | 1,904 ms
40,152 KB |
testcase_02 | AC | 1,870 ms
39,872 KB |
testcase_03 | AC | 1,985 ms
39,852 KB |
testcase_04 | AC | 2,089 ms
39,128 KB |
testcase_05 | AC | 1,974 ms
39,020 KB |
testcase_06 | AC | 1,121 ms
34,060 KB |
testcase_07 | AC | 1,474 ms
35,732 KB |
testcase_08 | AC | 1,488 ms
35,724 KB |
testcase_09 | AC | 1,479 ms
35,816 KB |
testcase_10 | AC | 1,542 ms
35,740 KB |
testcase_11 | AC | 1,549 ms
35,716 KB |
testcase_12 | AC | 1,530 ms
35,728 KB |
testcase_13 | AC | 1,531 ms
35,768 KB |
testcase_14 | AC | 1,412 ms
35,736 KB |
testcase_15 | AC | 1,425 ms
35,864 KB |
testcase_16 | AC | 1,357 ms
35,808 KB |
testcase_17 | AC | 773 ms
39,704 KB |
testcase_18 | AC | 213 ms
6,940 KB |
testcase_19 | AC | 214 ms
6,940 KB |
testcase_20 | AC | 210 ms
6,940 KB |
testcase_21 | AC | 195 ms
6,940 KB |
testcase_22 | AC | 203 ms
6,944 KB |
testcase_23 | AC | 170 ms
6,940 KB |
testcase_24 | AC | 183 ms
6,940 KB |
testcase_25 | AC | 183 ms
6,944 KB |
testcase_26 | AC | 179 ms
6,944 KB |
testcase_27 | AC | 181 ms
6,944 KB |
testcase_28 | AC | 177 ms
6,940 KB |
testcase_29 | AC | 1,686 ms
40,580 KB |
testcase_30 | AC | 1,550 ms
40,440 KB |
testcase_31 | AC | 1,512 ms
40,428 KB |
testcase_32 | AC | 1,102 ms
28,832 KB |
testcase_33 | AC | 858 ms
22,644 KB |
testcase_34 | AC | 1,369 ms
34,160 KB |
testcase_35 | AC | 376 ms
8,548 KB |
testcase_36 | AC | 1,182 ms
29,668 KB |
testcase_37 | AC | 1,126 ms
27,828 KB |
testcase_38 | AC | 1,135 ms
28,644 KB |
testcase_39 | AC | 729 ms
18,340 KB |
testcase_40 | AC | 257 ms
6,940 KB |
testcase_41 | AC | 1,142 ms
28,876 KB |
testcase_42 | AC | 2 ms
6,944 KB |
testcase_43 | AC | 2 ms
6,940 KB |
testcase_44 | AC | 2 ms
6,940 KB |
testcase_45 | AC | 1,109 ms
34,056 KB |
testcase_46 | AC | 1,058 ms
34,184 KB |
testcase_47 | AC | 1,071 ms
34,052 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1000000000; const int LOG = 18; struct lowest_common_ancestor{ vector<int> d; vector<vector<int>> p; lowest_common_ancestor(){ } lowest_common_ancestor(vector<int> &P, vector<vector<int>> &C){ int N = P.size(); d = vector<int>(N, 0); queue<int> Q; Q.push(0); while (!Q.empty()){ int v = Q.front(); Q.pop(); for (int w : C[v]){ d[w] = d[v] + 1; Q.push(w); } } p = vector<vector<int>>(LOG, vector<int>(N, -1)); for (int i = 0; i < N; i++){ p[0][i] = P[i]; } for (int i = 1; i < LOG; i++){ for (int j = 0; j < N; j++){ if (p[i - 1][j] != -1){ p[i][j] = p[i - 1][p[i - 1][j]]; } } } } int query(int u, int v){ if (d[u] > d[v]){ swap(u, v); } for (int k = 0; k < LOG; k++){ if ((d[v] - d[u]) >> k & 1){ v = p[k][v]; } } if (u == v){ return u; } for (int k = LOG - 1; k >= 0; k--){ if (p[k][u] != p[k][v]){ u = p[k][u]; v = p[k][v]; } } return p[0][u]; } }; template <typename T> struct binary_indexed_tree{ int N; vector<T> BIT; binary_indexed_tree(){ } binary_indexed_tree(int n){ N = 1; while (N < n){ N *= 2; } BIT = vector<T>(N + 1, 0); } void add(int i, T x){ i++; while (i <= N){ BIT[i] += x; i += i & -i; } } T sum(int i){ T ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } T query(int L, int R){ return sum(R) - sum(L); } }; template <typename T> struct euler_tour{ vector<T> A; vector<int> left; vector<int> right; binary_indexed_tree<T> BIT; void dfs(vector<vector<int>> &c, int v){ left[v] = A.size(); A.push_back(0); for (int w : c[v]){ dfs(c, w); } right[v] = A.size(); A.push_back(0); } euler_tour(vector<int> &p, vector<vector<int>> &c){ int N = p.size(); left = vector<int>(N); right = vector<int>(N); dfs(c, 0); BIT = binary_indexed_tree<int>(N * 2); } void add(int v){ BIT.add(left[v], 1); BIT.add(right[v], -1); } T query(int v, int w, int u){ return BIT.query(left[u], left[v] + 1) + BIT.query(left[u] + 1, left[w] + 1); } }; int main(){ int N; cin >> N; vector<vector<pair<long long, int>>> E(N); vector<tuple<int, int, int>> edges; for (int i = 0; i < N - 1; i++){ int u, v, w; cin >> u >> v >> w; u--; v--; E[u].push_back(make_pair(w, v)); E[v].push_back(make_pair(w, u)); edges.push_back(make_tuple(w, u, v)); } vector<int> p(N, -1); vector<vector<int>> c(N); vector<long long> s(N, 0); queue<int> q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (auto e : E[v]){ int d = e.first; int w = e.second; if (w != p[v]){ p[w] = v; c[v].push_back(w); s[w] = s[v] + d; q.push(w); } } } lowest_common_ancestor LCA(p, c); int Q; cin >> Q; vector<int> x(Q), y(Q), l(Q); for (int i = 0; i < Q; i++){ cin >> x[i] >> y[i]; x[i]--; y[i]--; l[i] = LCA.query(x[i], y[i]); } sort(edges.begin(), edges.end()); vector<int> tv(Q, N); vector<int> fv(Q, 0); while (1){ bool upd = false; vector<vector<int>> check(N - 1); for (int i = 0; i < Q; i++){ if (tv[i] - fv[i] > 1){ upd = true; int mid = (tv[i] + fv[i]) / 2; check[mid - 1].push_back(i); } } if (!upd){ break; } euler_tour<int> T1(p, c), T2(p, c); vector<bool> used(N, false); for (int i = 0; i < N - 1; i++){ int u = get<1>(edges[i]); int v = get<2>(edges[i]); T1.add(u); T1.add(v); if (u == p[v]){ T2.add(v); used[v] = true; } else { T2.add(u); used[u] = true; } for (int id : check[i]){ int a = T1.query(x[id], y[id], l[id]); int b = T2.query(x[id], y[id], l[id]); if (used[l[id]]){ b--; } if (a > b * 2){ tv[id] = i + 1; } else { fv[id] = i + 1; } } } } for (int i = 0; i < Q; i++){ if (tv[i] == N){ cout << -1 << endl; } else { cout << s[x[i]] + s[y[i]] - s[l[i]] * 2 + get<0>(edges[tv[i] - 1]) * 2 << endl; } } }