結果
問題 | No.1212 Second Path |
ユーザー | SSRS |
提出日時 | 2020-08-30 17:02:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,718 ms / 3,000 ms |
コード長 | 4,236 bytes |
コンパイル時間 | 5,082 ms |
コンパイル使用メモリ | 234,004 KB |
実行使用メモリ | 40,212 KB |
最終ジャッジ日時 | 2023-08-09 16:30:38 |
合計ジャッジ時間 | 55,647 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 807 ms
39,900 KB |
testcase_01 | AC | 1,655 ms
39,888 KB |
testcase_02 | AC | 1,695 ms
39,404 KB |
testcase_03 | AC | 1,694 ms
39,680 KB |
testcase_04 | AC | 1,718 ms
38,648 KB |
testcase_05 | AC | 1,712 ms
38,620 KB |
testcase_06 | AC | 1,022 ms
34,188 KB |
testcase_07 | AC | 1,372 ms
35,760 KB |
testcase_08 | AC | 1,386 ms
35,608 KB |
testcase_09 | AC | 1,405 ms
35,796 KB |
testcase_10 | AC | 1,430 ms
35,528 KB |
testcase_11 | AC | 1,458 ms
35,528 KB |
testcase_12 | AC | 1,417 ms
35,508 KB |
testcase_13 | AC | 1,393 ms
35,616 KB |
testcase_14 | AC | 1,386 ms
35,620 KB |
testcase_15 | AC | 1,445 ms
35,572 KB |
testcase_16 | AC | 1,394 ms
35,664 KB |
testcase_17 | AC | 756 ms
39,640 KB |
testcase_18 | AC | 201 ms
5,828 KB |
testcase_19 | AC | 203 ms
5,936 KB |
testcase_20 | AC | 197 ms
5,740 KB |
testcase_21 | AC | 190 ms
6,124 KB |
testcase_22 | AC | 196 ms
5,796 KB |
testcase_23 | AC | 161 ms
5,616 KB |
testcase_24 | AC | 173 ms
5,804 KB |
testcase_25 | AC | 172 ms
5,772 KB |
testcase_26 | AC | 173 ms
5,796 KB |
testcase_27 | AC | 170 ms
5,928 KB |
testcase_28 | AC | 168 ms
6,068 KB |
testcase_29 | AC | 1,482 ms
40,104 KB |
testcase_30 | AC | 1,641 ms
40,212 KB |
testcase_31 | AC | 1,525 ms
40,192 KB |
testcase_32 | AC | 1,144 ms
28,616 KB |
testcase_33 | AC | 825 ms
22,708 KB |
testcase_34 | AC | 1,291 ms
33,860 KB |
testcase_35 | AC | 360 ms
8,464 KB |
testcase_36 | AC | 1,148 ms
29,432 KB |
testcase_37 | AC | 1,061 ms
27,484 KB |
testcase_38 | AC | 1,077 ms
28,460 KB |
testcase_39 | AC | 687 ms
18,152 KB |
testcase_40 | AC | 244 ms
6,024 KB |
testcase_41 | AC | 1,111 ms
28,824 KB |
testcase_42 | AC | 2 ms
4,376 KB |
testcase_43 | AC | 2 ms
4,376 KB |
testcase_44 | AC | 2 ms
4,380 KB |
testcase_45 | AC | 1,074 ms
34,156 KB |
testcase_46 | AC | 1,093 ms
34,148 KB |
testcase_47 | AC | 1,093 ms
33,960 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; } } }