Submission #46386

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
#define swap(i,j) { int tmp = i; i = j; j = tmp; }
int n;
vector< pair<int, int> > graph[100010];
vector<int> tree[100010];
vector<int> subtree[100010];
int par[100010] = {};
int num[100010] = {};
int deep[100010] = {};
int vid[100010];
int nid[100010];
int head[100010];
int team[100010];
int dist[100010];
int size[100010] = {};
int b = 0;
bool used[100010] = {};
void maketree(int i){
used[i] = true;
for(int x = 0;x < graph[i].size();x++){
if(!used[graph[i][x].first]){
par[graph[i][x].first] = i;
dist[graph[i][x].first] = graph[i][x].second;
tree[i].push_back(graph[i][x].first);
maketree(graph[i][x].first);
}
}
}
int setnum(int i, int j, int k){
dist[i] = j+dist[i];
deep[i] = k;
if(tree[i].size() == 0) return num[i] = 1;
int ret = 1;
for(int x = 0;x < tree[i].size();x++){
ret += setnum(tree[i][x],dist[i],k+1);
}
return num[i] = ret;
}
void dis(int n){
memset(team,-1,sizeof(team));
priority_queue<pair<int, int> > que;
for(int i = 0;i < n;i++){
que.push(make_pair(num[i], i));
}
int gnum = 0;
int next;
int pos = 0;
int i;
while(!que.empty()){
i = que.top().second; que.pop();
if(team[i] != -1) continue;
team[i] = gnum;
size[gnum]++;
subtree[gnum].push_back(i);
nid[i] = 0;
int nn = 1;
head[i] = i;
vid[i] = pos;
pos++;
next = i;
while(tree[next].size() != 0){
int maxi = 0;
for(int j = 1;j < tree[next].size();j++){
if(num[tree[next][maxi]] < num[tree[next][j]]){
maxi = j;
}
}
subtree[gnum].push_back(tree[next][maxi]);
team[tree[next][maxi]] = gnum;
head[tree[next][maxi]] = i;
vid[tree[next][maxi]] = pos;
nid[tree[next][maxi]] = nn;
size[gnum]++;
pos++;
nn++;
next = tree[next][maxi];
}
gnum++;
}
return;
}
void build(int n){
maketree(0);
setnum(0,0,0);
dis(n);
return;
}
int lca(int i, int j){
while(1){
if(vid[i] > vid[j]) swap(i, j);
if(head[i] == head[j]) return i;
j = par[head[j]];
}
}
int getdist(int i, int j){
return dist[i] + dist[j] - 2 * dist[lca(i, j)];
}
int getlen(int i, int j){
return deep[i] + deep[j] - 2 * deep[lca(i, j)];
}
int treeSearch(int a, int m){
if(size[team[a]] - (size[team[a]]-nid[a]-1) > m){
return subtree[team[a]][nid[a]-m];
}else{
return treeSearch(par[head[a]],m-(size[team[a]]-(size[team[a]]-nid[a]-1)));
}
}
int x, y, z;
int maxdist(int i){
return max(getdist(x,i), max(getdist(y,i),getdist(z,i)));
}
int ordist(int i,int a){
return max(getdist(x,i) * (x != a), max(getdist(y,i) * (y != a) ,getdist(z,i) * (z != a)));
}
int path(int u, int v, int d){
if(d == 0) return 0;
int r = lca(u, v);
int x = getlen(u, r), y = getlen(r, v);
if(d <= x) return treeSearch(u,d);
return treeSearch(v,(x+y)-d);
}
int search(int u, int v, int ans){
if(ordist(v, u) >= ans) return ans;
int left = 0;
int right = getlen(u, v);
int dat, mid;
while(left+1 < right){
mid = (left + right) / 2;
dat = path(u,v,mid);
if(ordist(dat,u) < getdist(dat,u)){
right = mid;
}else{
left = mid;
}
}
return min(ans,min(maxdist(path(u,v,left)),maxdist(path(u,v,right))));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> n >> q;
int a, b, c;
for(int i = 0;i < n-1;i++){
cin >> a >> b >> c;
a--; b--;
graph[a].push_back(make_pair(b,c));
graph[b].push_back(make_pair(a,c));
}
build(n);
int mid;
int ans;
for(int i = 0;i < q;i++){
cin >> x >> y >> z;
x--; y--; z--;
a = lca(x,y); b = lca(y,z); c = lca(z,x);
mid = deep[a] > deep[b] ? (deep[a] > deep[c] ? a : c) : (deep[b] > deep[c] ? b : c);
ans = min(maxdist(x), min(maxdist(y), min(maxdist(z), maxdist(mid))));
ans = search(x,mid,ans);
ans = search(y,mid,ans);
ans = search(z,mid,ans);
cout << ans << endl;
}
return 0;
}

ステータス

項目 データ
問題 1024 - 待ち合わせ
ユーザー名 ei1719
投稿日時 2019-01-01 00:35:41
言語 C++11
状態 Accepted
得点 14
ソースコード長 4200 Byte
最大実行時間 412 ms
最大メモリ使用量 31736 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 26 ms 9564 KB
1
in2.txt AC 19 ms 9680 KB
1
in3.txt AC 25 ms 9632 KB
1
in4.txt AC 23 ms 11740 KB
1
in5.txt AC 23 ms 16316 KB
1
in6.txt AC 22 ms 21400 KB
1
in7.txt AC 20 ms 21428 KB
1
in8.txt AC 22 ms 21324 KB
1
in9.txt AC 24 ms 21352 KB
1
in10.txt AC 30 ms 9464 KB
1
in11.txt AC 22 ms 9492 KB
1
in12.txt AC 45 ms 9384 KB
1
in13.txt AC 22 ms 9412 KB
1
in14.txt AC 24 ms 9440 KB
1
in15.txt AC 22 ms 9460 KB
1
in16.txt AC 27 ms 9608 KB
1
in17.txt AC 25 ms 9628 KB
1
in18.txt AC 26 ms 9644 KB
1
in19.txt AC 24 ms 9664 KB
1
in20.txt AC 30 ms 9584 KB
1
in21.txt AC 20 ms 9732 KB
1
in22.txt AC 22 ms 9624 KB
1
in23.txt AC 27 ms 9640 KB
1
in24.txt AC 30 ms 9532 KB
1
in25.txt AC 31 ms 9552 KB
1
in26.txt AC 29 ms 9692 KB
1
in27.txt AC 23 ms 9712 KB
1
in28.txt AC 29 ms 9596 KB
1
in29.txt AC 29 ms 9616 KB
1
in30.txt AC 30 ms 9660 KB
1
in31.txt AC 29 ms 9672 KB
1
in32.txt AC 24 ms 9688 KB
1
in33.txt AC 28 ms 9708 KB
1
in34.txt AC 34 ms 9596 KB
1
in35.txt AC 25 ms 9744 KB
1
in36.txt AC 310 ms 25108 KB
1
in37.txt AC 400 ms 18916 KB
1
in38.txt AC 412 ms 18404 KB
1
in39.txt AC 398 ms 20348 KB
1
in40.txt AC 400 ms 19432 KB
1
in41.txt AC 356 ms 20320 KB
1
in42.txt AC 232 ms 21720 KB
1
in43.txt AC 263 ms 20552 KB
1
in44.txt AC 285 ms 20716 KB
1
in45.txt AC 298 ms 22836 KB
1
in46.txt AC 328 ms 23136 KB
1
in47.txt AC 398 ms 22972 KB
1
in48.txt AC 394 ms 24100 KB
1
in49.txt AC 339 ms 24136 KB
1
in50.txt AC 369 ms 24656 KB
1
in51.txt AC 346 ms 25824 KB
1
in52.txt AC 342 ms 28852 KB
1
in53.txt AC 339 ms 30064 KB
1
in54.txt AC 317 ms 30048 KB
1
in55.txt AC 317 ms 31312 KB
1
in56.txt AC 335 ms 31736 KB
1