Submission #68040

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
using namespace std;
template<typename Graph>
struct Doubling {
public:
int n, lg;
const Graph g;
vector<int> depth;
vector<vector<int> > table, dist_table;
vector<int> dist;
Doubling(Graph &G) : g(G), n(G.size()), depth(G.size()), dist(G.size()) {
lg = 32 - __builtin_clz(n) + 1;
table.resize(n, vector(lg, 0));
dist_table.resize(n, vector(lg, 0));
dfs(0, -1, 0, 0);
build();
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int k = lg - 1; k >= 0; --k) {
if (depth[u] - depth[v] >> k & 1) u = table[u][k];
}
if (u == v) return (u);
for (int k = lg - 1; k >= 0; --k) {
if (table[u][k] != table[v][k]) {
u = table[u][k];
v = table[v][k];
}
}
return (table[u][0]);
}
/* dep[u] < dep[v] */
int binary_search(int u, int v, int all) {
int sum = 0;
for (int k = lg - 1; k >= 0; --k) {
if (depth[v] - depth[u] >= 1 << k && (sum + dist_table[v][k]) * 2 < all) {
sum += dist_table[v][k];
v = table[v][k];
}
}
return (v);
}
int la(int u, int x) {
for (int k = lg - 1; k >= 0; --k) {
if (x >> k & 1) {
u = table[u][k];
x >>= 1;
}
}
return (u);
}
int distance(int u, int v) {
return (dist[u] + dist[v] - dist[lca(u, v)] * 2);
}
private:
void build() {
for (int k = 0; k < lg - 1; ++k) {
for (int i = 0; i < n; ++i) {
if (table[i][k] != -1) {
table[i][k + 1] = table[table[i][k]][k];
dist_table[i][k + 1] = dist_table[i][k] + dist_table[table[i][k]][k];
}
}
}
}
void dfs(int cur, int par, int dep, int dis) {
depth[cur] = dep;
table[cur][0] = par;
dist[cur] = dis;
for (auto [to, w] : g[cur]) {
if (par == to) continue;
dist_table[to][0] = w;
dfs(to, cur, dep + 1, dis + w);
}
}
};
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<vector<pair<int, int> > > graph(n);
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
Doubling dbl(graph);
for (int i = 0; i < q; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a, --b, --c;
int dist_ab = dbl.distance(a, b);
int dist_ac = dbl.distance(a, c);
int dist_bc = dbl.distance(b, c);
int max_dist = max({dist_ab, dist_ac, dist_bc});
int u, v;
if (dist_ab == max_dist) u = a, v = b;
if (dist_ac == max_dist) u = a, v = c;
if (dist_bc == max_dist) u = b, v = c;
int lca = dbl.lca(u, v), dist = max_dist;
if (dbl.depth[u] > dbl.depth[v]) swap(u, v);
if (lca != u) {
if (dbl.distance(u, lca) > dbl.distance(lca, v)) swap(u, v);
u = lca;
}
// cout << u << ' ' << v << ' ' << dist << '\n';
int x = dbl.binary_search(u, v, dist);
int y = max(dbl.la(x, 1), 0);
// cout << x << ' ' << y << '\n';
cout << min(max({dbl.distance(a, x), dbl.distance(b, x), dbl.distance(c, x)}),
max({dbl.distance(a, y), dbl.distance(b, y), dbl.distance(c, y)})) << '\n';
}
return (0);
}

ステータス

項目 データ
問題 1024 - 待ち合わせ
ユーザー名 ei1903
投稿日時 2021-08-11 11:05:44
言語 C++17
状態 Accepted
得点 14
ソースコード長 3818 Byte
最大実行時間 521 ms
最大メモリ使用量 45792 KB

セット

セット 得点 Cases
1 ALL 14 / 14 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 28 ms 600 KB
1
in2.txt AC 29 ms 640 KB
1
in3.txt AC 17 ms 632 KB
1
in4.txt AC 25 ms 2756 KB
1
in5.txt AC 19 ms 7420 KB
1
in6.txt AC 27 ms 12268 KB
1
in7.txt AC 24 ms 12348 KB
1
in8.txt AC 22 ms 12300 KB
1
in9.txt AC 20 ms 12372 KB
1
in10.txt AC 29 ms 420 KB
1
in11.txt AC 22 ms 620 KB
1
in12.txt AC 21 ms 572 KB
1
in13.txt AC 17 ms 528 KB
1
in14.txt AC 28 ms 484 KB
1
in15.txt AC 30 ms 556 KB
1
in16.txt AC 20 ms 628 KB
1
in17.txt AC 21 ms 572 KB
1
in18.txt AC 24 ms 640 KB
1
in19.txt AC 18 ms 580 KB
1
in20.txt AC 18 ms 596 KB
1
in21.txt AC 20 ms 660 KB
1
in22.txt AC 15 ms 592 KB
1
in23.txt AC 18 ms 652 KB
1
in24.txt AC 22 ms 712 KB
1
in25.txt AC 16 ms 648 KB
1
in26.txt AC 21 ms 704 KB
1
in27.txt AC 26 ms 752 KB
1
in28.txt AC 25 ms 668 KB
1
in29.txt AC 24 ms 716 KB
1
in30.txt AC 15 ms 716 KB
1
in31.txt AC 20 ms 764 KB
1
in32.txt AC 22 ms 680 KB
1
in33.txt AC 21 ms 592 KB
1
in34.txt AC 20 ms 636 KB
1
in35.txt AC 21 ms 812 KB
1
in36.txt AC 494 ms 41180 KB
1
in37.txt AC 219 ms 32392 KB
1
in38.txt AC 229 ms 29144 KB
1
in39.txt AC 242 ms 35412 KB
1
in40.txt AC 239 ms 30612 KB
1
in41.txt AC 232 ms 32300 KB
1
in42.txt AC 158 ms 35056 KB
1
in43.txt AC 174 ms 31156 KB
1
in44.txt AC 219 ms 31376 KB
1
in45.txt AC 215 ms 37888 KB
1
in46.txt AC 232 ms 37676 KB
1
in47.txt AC 309 ms 36048 KB
1
in48.txt AC 393 ms 38468 KB
1
in49.txt AC 336 ms 37704 KB
1
in50.txt AC 363 ms 37452 KB
1
in51.txt AC 399 ms 40132 KB
1
in52.txt AC 391 ms 42864 KB
1
in53.txt AC 465 ms 45340 KB
1
in54.txt AC 447 ms 43356 KB
1
in55.txt AC 521 ms 45500 KB
1
in56.txt AC 467 ms 45792 KB
1