Submission #62871

ソースコード

?
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
#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, wei, inv, type;
/*
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]];
}
}
// 頂点 v から k 個上った頂点
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];
}
}
// u, v 間の辺の個数
int distance(int u,int v) const {
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
// u, v間の辺のコストの総和
Type pathWeight(int u, int v) const {
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;
int q;
cin >> n >> q;
HLD<int> hl(n);
for(int i = 1; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
hl.add_edge(a-1, b-1, c);
}
hl.build();
while(q--) {
int a, b, c;
cin >> a >> b >> c;
a--, b--, c--;
int c1 = hl.pathWeight(a, b);
int c2 = hl.pathWeight(a, c);
int c3 = hl.pathWeight(b, c);
if(max({c1, c2, c3}) == c2) {
b = c;
}
else if(max({c1, c2, c3}) == c3) {
a = c;
}
auto binSerach = [&](int s, int e) {
int lca = hl.lca(s, e);
int l = 0;
int r = hl.distance(s, lca) + 1;
while(abs(l - r) > 1) {
int m = (l + r) / 2;
int p = hl.climb(s, m);
int x = hl.pathWeight(s, p), y = hl.pathWeight(p, e);
(x < y ? l : r) = m;
}
int pl = hl.climb(s, l), pr = hl.climb(s, r);
return min(max(hl.pathWeight(s, pl), hl.pathWeight(pl, e)),
max(hl.pathWeight(s, pr), hl.pathWeight(pr, e)));
};
int lca = hl.lca(a, b);
cout << min(binSerach(a, b), binSerach(b, a)) << endl;
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 37 ms 604 KB
1
in2.txt AC 20 ms 680 KB
1
in3.txt AC 20 ms 692 KB
1
in4.txt AC 23 ms 14688 KB
1
in5.txt AC 21 ms 47684 KB
1
in6.txt AC 18 ms 74092 KB
1
in7.txt AC 21 ms 74044 KB
1
in8.txt AC 16 ms 73996 KB
1
in9.txt AC 15 ms 73952 KB
1
in10.txt AC 25 ms 432 KB
1
in11.txt AC 42 ms 376 KB
1
in12.txt AC 19 ms 452 KB
1
in13.txt AC 30 ms 528 KB
1
in14.txt AC 21 ms 604 KB
1
in15.txt AC 17 ms 556 KB
1
in16.txt AC 20 ms 376 KB
1
in17.txt AC 24 ms 456 KB
1
in18.txt AC 21 ms 528 KB
1
in19.txt AC 25 ms 604 KB
1
in20.txt AC 21 ms 632 KB
1
in21.txt AC 24 ms 708 KB
1
in22.txt AC 26 ms 788 KB
1
in23.txt AC 25 ms 732 KB
1
in24.txt AC 23 ms 676 KB
1
in25.txt AC 19 ms 744 KB
1
in26.txt AC 62 ms 816 KB
1
in27.txt AC 27 ms 752 KB
1
in28.txt AC 19 ms 688 KB
1
in29.txt AC 26 ms 628 KB
1
in30.txt AC 23 ms 768 KB
1
in31.txt AC 45 ms 704 KB
1
in32.txt AC 21 ms 640 KB
1
in33.txt AC 24 ms 832 KB
1
in34.txt AC 22 ms 1024 KB
1
in35.txt AC 23 ms 968 KB
1
in36.txt AC 244 ms 21008 KB
1
in37.txt AC 267 ms 16960 KB
1
in38.txt AC 262 ms 19156 KB
1
in39.txt AC 285 ms 24364 KB
1
in40.txt AC 276 ms 26292 KB
1
in41.txt AC 295 ms 29784 KB
1
in42.txt AC 178 ms 33180 KB
1
in43.txt AC 192 ms 34976 KB
1
in44.txt AC 201 ms 37912 KB
1
in45.txt AC 219 ms 42964 KB
1
in46.txt AC 237 ms 46040 KB
1
in47.txt AC 238 ms 48132 KB
1
in48.txt AC 327 ms 52736 KB
1
in49.txt AC 243 ms 56060 KB
1
in50.txt AC 262 ms 59544 KB
1
in51.txt AC 255 ms 63708 KB
1
in52.txt AC 227 ms 70172 KB
1
in53.txt AC 248 ms 74584 KB
1
in54.txt AC 233 ms 77396 KB
1
in55.txt AC 271 ms 81940 KB
1
in56.txt AC 270 ms 85668 KB
1