Submission #62079

ソースコード

?
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
// #define int long long
struct IoSetup {
IoSetup() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
}IoSetup;
using Int = int;
using ll = long long;
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int SMOD = 1000000007;
constexpr int NMOD = 998244353;
constexpr int dx[]={1,0,-1,0,1,1,-1,-1};
constexpr int dy[]={0,-1,0,1,-1,1,-1,1};
inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T&b){if(a<b)return(a=b,1);return 0;}
template<class T>bool chmin(T &a, const T&b){if(b<a)return(a=b,1);return 0;}
template<typename T>
struct Edge {
int from, to;
T cost;
Edge(int to) : from(0), to(to), cost(T(1)) {}
Edge(int to, T cost) : from(0), to(to), cost(cost) {}
Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
const bool operator < (const Edge&e) const {
return (this->cost == e.cost ? (this->from == e.from ? this->to < e.to : this->from < e.from) : this->cost < e.cost);
}
};
template<typename T>
using Graph = vector<vector<Edge<T>>>;
template<typename T>
using Edges = vector<Edge<T>>;
template<typename Type>
class HLD {
private:
void dfs_sz(int v) {
for(auto &u:G[v])
if(u.to==par[v]) swap(u,G[v].back());
if(~par[v]) G[v].pop_back();
for(auto &u:G[v]){
par[u.to]=v;
dep[u.to]=dep[v]+1;
wei[u.to] = wei[v] + u.cost;
dfs_sz(u.to);
sub[v]+=sub[u.to];
if(sub[u.to]>sub[G[v][0].to]) swap(u,G[v][0]);
}
}
void dfs_hld(int v,int c,int &pos) {
vid[v]=pos++;
inv[vid[v]]=v;
type[v]=c;
for(auto& u:G[v]){
if(u.to==par[v]) continue;
head[u.to]=(u.to==G[v][0].to?head[v]:u.to);
dfs_hld(u.to,c,pos);
}
}
public:
vector< vector<Edge<Type>> > G;
vector<int> vid, head, sub, par, dep, inv, type, wei;
/*
vid : HL分解後でのグラフでのid
head: 頂点が属するheavy-pathのheadのid
sub : 部分木のサイズ
hvy : heavy-path上での次の頂点のid
par : 親のid
dep : 深さ
wei : 根からのコストの総和
inv : HL分解前のid(添え字が分解後のid)
type: 森をHL分解するときの属する木の番号
*/
HLD(int n):
G(n),vid(n,-1),head(n),sub(n,1),
par(n,-1),dep(n,0),wei(n, 0), inv(n),type(n){}
// u <--> v
void add_edge(int u,int v, Type cost = 1) {
G[u].emplace_back(Edge<Type>(v, cost));
G[v].emplace_back(Edge<Type>(u, cost));
}
void build(vector<int> rs={0}) {
int c=0,pos=0;
for(int r:rs){
dfs_sz(r);
head[r]=r;
dfs_hld(r,c++,pos);
}
}
int lca(int u,int v) const {
while(1){
if(vid[u]>vid[v]) swap(u,v);
if(head[u]==head[v]) return u;
v=par[head[v]];
}
}
int climb(int v, int k) const {
while(true) {
const int h = head[v];
if(vid[v] - k >= vid[h]) return inv[vid[v] - k];
k -= vid[v] - vid[h] + 1;
v = par[h];
}
}
int distance(int u,int v) {
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
Type pathWeight(int u, int v) {
return wei[u] + wei[v] - 2 * wei[lca(u, v)];
}
// for_each(vertex)
// [l, r) <- attention!!
template<typename F>
void for_each(int u, int v, const F& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
f(max(vid[head[v]],vid[u]),vid[v]+1);
if(head[u]!=head[v]) v=par[head[v]];
else break;
}
}
template<typename T,typename Q,typename F>
T for_each(int u,int v,T ti,const Q &q,const F &f){
T l=ti,r=ti;
while(1){
if(vid[u]>vid[v]){
swap(u,v);
swap(l,r);
}
l=f(l,q(max(vid[head[v]],vid[u]),vid[v]+1));
if(head[u]!=head[v]) v=par[head[v]];
else break;
}
return f(l,r);
}
// for_each(edge)
// [l, r) <- attention!!
template<typename F>
void for_each_edge(int u, int v,const F& f) {
while(1){
if(vid[u]>vid[v]) swap(u,v);
if(head[u]!=head[v]){
f(vid[head[v]],vid[v]+1);
v=par[head[v]];
}else{
if(u!=v) f(vid[u]+1,vid[v]+1);
break;
}
}
}
};
signed main() {
int n, q;
cin >> n >> q;
HLD<int> hl(n);
vector<int> U(n), V(n), W(n);
for(int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
U[i] = a; V[i] = b; W[i] = c;
hl.add_edge(a, b, c);
}
hl.build();
while(q--) {
int a, b, c;
cin >> a >> b >> c;
a--, b--, c--;
int ret[3] = {};
ret[0] = hl.pathWeight(a, b);
ret[1] = hl.pathWeight(a, c);
ret[2] = hl.pathWeight(b, c);
if(max({ret[0], ret[1], ret[2]}) == ret[1]) {
b = c;
}
else if(max({ret[0], ret[1], ret[2]}) == ret[2]) {
a = b;
b = c;
}
int lca = hl.lca(a, b);
int l = 0, r = hl.distance(a, b) + 1;
const auto binSearch = [&](int s, int lca, int t) -> int {
int ret = INF;
int l = 0, r = hl.distance(s, lca) + 1;
while(abs(l - r) > 1) {
int m = (l + r) / 2;
int p = hl.climb(s, m);
(hl.pathWeight(s, p) < hl.pathWeight(p, t) ? l : r) = m;
}
int p = hl.climb(s, l);
chmin(ret, max(hl.pathWeight(s, p), hl.pathWeight(p, t)));
p = hl.climb(s, r);
chmin(ret, max(hl.pathWeight(s, p), hl.pathWeight(p, t)));
return ret;
};
cout << min(binSearch(a, lca, b), binSearch(b, lca, a)) << endl;
}
return 0;
}

ステータス

項目 データ
問題 1024 - 待ち合わせ
ユーザー名 ei1821
投稿日時 2020-08-13 12:40:11
言語 C++17
状態 Accepted
得点 14
ソースコード長 6605 Byte
最大実行時間 328 ms
最大メモリ使用量 25068 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 22 ms 604 KB
1
in2.txt AC 23 ms 672 KB
1
in3.txt AC 18 ms 688 KB
1
in4.txt AC 26 ms 2864 KB
1
in5.txt AC 22 ms 7388 KB
1
in6.txt AC 17 ms 12272 KB
1
in7.txt AC 22 ms 12356 KB
1
in8.txt AC 17 ms 12436 KB
1
in9.txt AC 26 ms 12516 KB
1
in10.txt AC 20 ms 428 KB
1
in11.txt AC 22 ms 376 KB
1
in12.txt AC 17 ms 576 KB
1
in13.txt AC 21 ms 524 KB
1
in14.txt AC 32 ms 604 KB
1
in15.txt AC 15 ms 556 KB
1
in16.txt AC 21 ms 500 KB
1
in17.txt AC 20 ms 572 KB
1
in18.txt AC 28 ms 516 KB
1
in19.txt AC 22 ms 596 KB
1
in20.txt AC 21 ms 624 KB
1
in21.txt AC 28 ms 576 KB
1
in22.txt AC 21 ms 648 KB
1
in23.txt AC 33 ms 592 KB
1
in24.txt AC 32 ms 668 KB
1
in25.txt AC 17 ms 480 KB
1
in26.txt AC 23 ms 552 KB
1
in27.txt AC 22 ms 620 KB
1
in28.txt AC 20 ms 560 KB
1
in29.txt AC 23 ms 624 KB
1
in30.txt AC 20 ms 768 KB
1
in31.txt AC 21 ms 704 KB
1
in32.txt AC 18 ms 644 KB
1
in33.txt AC 28 ms 584 KB
1
in34.txt AC 17 ms 648 KB
1
in35.txt AC 26 ms 716 KB
1
in36.txt AC 278 ms 19084 KB
1
in37.txt AC 305 ms 11944 KB
1
in38.txt AC 304 ms 11120 KB
1
in39.txt AC 309 ms 13576 KB
1
in40.txt AC 311 ms 12288 KB
1
in41.txt AC 277 ms 13256 KB
1
in42.txt AC 226 ms 14084 KB
1
in43.txt AC 243 ms 13128 KB
1
in44.txt AC 248 ms 13436 KB
1
in45.txt AC 256 ms 15876 KB
1
in46.txt AC 267 ms 15980 KB
1
in47.txt AC 263 ms 15272 KB
1
in48.txt AC 328 ms 16740 KB
1
in49.txt AC 284 ms 16860 KB
1
in50.txt AC 292 ms 17328 KB
1
in51.txt AC 287 ms 18640 KB
1
in52.txt AC 252 ms 22052 KB
1
in53.txt AC 288 ms 23456 KB
1
in54.txt AC 280 ms 23056 KB
1
in55.txt AC 302 ms 24496 KB
1
in56.txt AC 289 ms 25068 KB
1