Submission #61968

ソースコード

?
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
#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);
chmin(ret, max(hl.pathWeight(s, p), hl.pathWeight(p, t)));
(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)));
return ret;
};
cout << min(binSearch(a, lca, b), binSearch(b, lca, a)) << endl;
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 36 ms 604 KB
1
in2.txt AC 18 ms 556 KB
1
in3.txt AC 27 ms 716 KB
1
in4.txt AC 25 ms 14664 KB
1
in5.txt AC 27 ms 47592 KB
1
in6.txt AC 22 ms 73972 KB
1
in7.txt AC 19 ms 73928 KB
1
in8.txt AC 27 ms 73880 KB
1
in9.txt AC 21 ms 73960 KB
1
in10.txt AC 20 ms 436 KB
1
in11.txt AC 26 ms 512 KB
1
in12.txt AC 21 ms 460 KB
1
in13.txt AC 27 ms 540 KB
1
in14.txt AC 24 ms 616 KB
1
in15.txt AC 26 ms 568 KB
1
in16.txt AC 26 ms 516 KB
1
in17.txt AC 31 ms 460 KB
1
in18.txt AC 18 ms 532 KB
1
in19.txt AC 32 ms 608 KB
1
in20.txt AC 25 ms 640 KB
1
in21.txt AC 22 ms 584 KB
1
in22.txt AC 26 ms 664 KB
1
in23.txt AC 29 ms 600 KB
1
in24.txt AC 24 ms 540 KB
1
in25.txt AC 31 ms 612 KB
1
in26.txt AC 42 ms 684 KB
1
in27.txt AC 26 ms 756 KB
1
in28.txt AC 22 ms 700 KB
1
in29.txt AC 30 ms 772 KB
1
in30.txt AC 17 ms 800 KB
1
in31.txt AC 27 ms 868 KB
1
in32.txt AC 45 ms 808 KB
1
in33.txt AC 26 ms 744 KB
1
in34.txt AC 31 ms 808 KB
1
in35.txt AC 31 ms 876 KB
1
in36.txt AC 301 ms 22320 KB
1
in37.txt AC 308 ms 18116 KB
1
in38.txt AC 313 ms 20104 KB
1
in39.txt AC 369 ms 25504 KB
1
in40.txt AC 324 ms 27420 KB
1
in41.txt AC 313 ms 30812 KB
1
in42.txt AC 224 ms 34332 KB
1
in43.txt AC 244 ms 35936 KB
1
in44.txt AC 246 ms 38924 KB
1
in45.txt AC 250 ms 44180 KB
1
in46.txt AC 289 ms 47360 KB
1
in47.txt AC 301 ms 49464 KB
1
in48.txt AC 331 ms 54000 KB
1
in49.txt AC 319 ms 57064 KB
1
in50.txt AC 319 ms 60604 KB
1
in51.txt AC 306 ms 64856 KB
1
in52.txt AC 351 ms 71212 KB
1
in53.txt AC 303 ms 75936 KB
1
in54.txt AC 296 ms 78484 KB
1
in55.txt AC 324 ms 83128 KB
1
in56.txt AC 299 ms 86640 KB
1