| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 557683 |
2022-05-05T19:08:49 Z |
peteza |
Race (IOI11_race) |
C++14 |
|
456 ms |
36248 KB |
#include <iostream>
#include <utility>
#include <vector>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
const int mxn = 200005;
pii dist[1000005];
vector<pii> adj[mxn];
int SOL = 1000005, kk;
int sz[mxn];
int cent, d2 = 1, dep;
bool rem[mxn], fil;
int getsz(int cur, int p) {
sz[cur] = 1;
for(pii e:adj[cur])
if(e.first != p && !rem[e.first])
sz[cur] += getsz(e.first, cur);
return sz[cur];
}
int getcent(int tgt, int cur, int p) {
for(pii e:adj[cur])
if(e.first != p && !rem[e.first] && sz[e.first] > tgt/2)
return getcent(tgt, e.first, cur);
return cur;
}
void sol(int cur, int p) {
if(dep > kk) return ;
if(fil) {
if(dist[dep].first == cent)
dist[dep].second = min(d2, dist[dep].second);
else
dist[dep] = {cent, d2};
}
else if(dist[kk-dep].first == cent) SOL = min(dist[kk-dep].second+d2, SOL);
d2++;
for(pii e:adj[cur])
if(e.first != p && !rem[e.first])
{
dep += e.second;
sol(e.first, cur);
dep -= e.second;
}
d2--;
}
void decompose(int cur) {
cent = getcent(getsz(cur, -1), cur, -1);
rem[cent] = 1;
dist[0] = {cent, 0};
for(pii e:adj[cent]) {
if(rem[e.first]) continue;
dep = e.second;
fil = 0; sol(e.first, cent);
fil = 1; sol(e.first, cent);
}
//cout << SOL << ' ' << cent << '\n';
for(pii e:adj[cent])
if(!rem[e.first]) decompose(e.first);
}
int best_path(int N, int K, int H[][2], int L[]) {
//assert(N <= 150'000);
kk = K;
fill(dist, dist+1000003, pii(-1, -1));
for(int i=0;i<N-1;i++) {
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
decompose(1);
return (SOL > N ? -1 : SOL);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12816 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 5 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 7 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12796 KB |
Output is correct |
| 11 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 12 |
Correct |
7 ms |
12856 KB |
Output is correct |
| 13 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 14 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 16 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 17 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 18 |
Correct |
7 ms |
12756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12816 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 5 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 7 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12796 KB |
Output is correct |
| 11 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 12 |
Correct |
7 ms |
12856 KB |
Output is correct |
| 13 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 14 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 16 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 17 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 18 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 19 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 20 |
Correct |
7 ms |
12808 KB |
Output is correct |
| 21 |
Correct |
7 ms |
12792 KB |
Output is correct |
| 22 |
Correct |
9 ms |
12884 KB |
Output is correct |
| 23 |
Correct |
7 ms |
12812 KB |
Output is correct |
| 24 |
Correct |
7 ms |
12824 KB |
Output is correct |
| 25 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 26 |
Correct |
7 ms |
12892 KB |
Output is correct |
| 27 |
Correct |
7 ms |
12856 KB |
Output is correct |
| 28 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 29 |
Correct |
7 ms |
12904 KB |
Output is correct |
| 30 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 31 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 32 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 33 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 34 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 35 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 36 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 37 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 38 |
Correct |
7 ms |
12884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12816 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 5 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 7 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12796 KB |
Output is correct |
| 11 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 12 |
Correct |
7 ms |
12856 KB |
Output is correct |
| 13 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 14 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 16 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 17 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 18 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 19 |
Correct |
126 ms |
18048 KB |
Output is correct |
| 20 |
Correct |
116 ms |
18132 KB |
Output is correct |
| 21 |
Correct |
131 ms |
18068 KB |
Output is correct |
| 22 |
Correct |
123 ms |
18136 KB |
Output is correct |
| 23 |
Correct |
81 ms |
18336 KB |
Output is correct |
| 24 |
Correct |
52 ms |
18252 KB |
Output is correct |
| 25 |
Correct |
125 ms |
23264 KB |
Output is correct |
| 26 |
Correct |
90 ms |
23848 KB |
Output is correct |
| 27 |
Correct |
164 ms |
23688 KB |
Output is correct |
| 28 |
Correct |
264 ms |
34092 KB |
Output is correct |
| 29 |
Correct |
247 ms |
29872 KB |
Output is correct |
| 30 |
Correct |
165 ms |
23644 KB |
Output is correct |
| 31 |
Correct |
188 ms |
23652 KB |
Output is correct |
| 32 |
Correct |
212 ms |
23692 KB |
Output is correct |
| 33 |
Correct |
206 ms |
22520 KB |
Output is correct |
| 34 |
Correct |
194 ms |
22476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12816 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 5 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 7 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12796 KB |
Output is correct |
| 11 |
Correct |
8 ms |
12756 KB |
Output is correct |
| 12 |
Correct |
7 ms |
12856 KB |
Output is correct |
| 13 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 14 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 16 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 17 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 18 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 19 |
Correct |
6 ms |
12756 KB |
Output is correct |
| 20 |
Correct |
7 ms |
12808 KB |
Output is correct |
| 21 |
Correct |
7 ms |
12792 KB |
Output is correct |
| 22 |
Correct |
9 ms |
12884 KB |
Output is correct |
| 23 |
Correct |
7 ms |
12812 KB |
Output is correct |
| 24 |
Correct |
7 ms |
12824 KB |
Output is correct |
| 25 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 26 |
Correct |
7 ms |
12892 KB |
Output is correct |
| 27 |
Correct |
7 ms |
12856 KB |
Output is correct |
| 28 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 29 |
Correct |
7 ms |
12904 KB |
Output is correct |
| 30 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 31 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 32 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 33 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 34 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 35 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 36 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 37 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 38 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 39 |
Correct |
126 ms |
18048 KB |
Output is correct |
| 40 |
Correct |
116 ms |
18132 KB |
Output is correct |
| 41 |
Correct |
131 ms |
18068 KB |
Output is correct |
| 42 |
Correct |
123 ms |
18136 KB |
Output is correct |
| 43 |
Correct |
81 ms |
18336 KB |
Output is correct |
| 44 |
Correct |
52 ms |
18252 KB |
Output is correct |
| 45 |
Correct |
125 ms |
23264 KB |
Output is correct |
| 46 |
Correct |
90 ms |
23848 KB |
Output is correct |
| 47 |
Correct |
164 ms |
23688 KB |
Output is correct |
| 48 |
Correct |
264 ms |
34092 KB |
Output is correct |
| 49 |
Correct |
247 ms |
29872 KB |
Output is correct |
| 50 |
Correct |
165 ms |
23644 KB |
Output is correct |
| 51 |
Correct |
188 ms |
23652 KB |
Output is correct |
| 52 |
Correct |
212 ms |
23692 KB |
Output is correct |
| 53 |
Correct |
206 ms |
22520 KB |
Output is correct |
| 54 |
Correct |
194 ms |
22476 KB |
Output is correct |
| 55 |
Correct |
18 ms |
13268 KB |
Output is correct |
| 56 |
Correct |
19 ms |
13248 KB |
Output is correct |
| 57 |
Correct |
98 ms |
18308 KB |
Output is correct |
| 58 |
Correct |
37 ms |
18340 KB |
Output is correct |
| 59 |
Correct |
99 ms |
25216 KB |
Output is correct |
| 60 |
Correct |
437 ms |
31808 KB |
Output is correct |
| 61 |
Correct |
169 ms |
26716 KB |
Output is correct |
| 62 |
Correct |
172 ms |
26656 KB |
Output is correct |
| 63 |
Correct |
264 ms |
26656 KB |
Output is correct |
| 64 |
Correct |
456 ms |
26864 KB |
Output is correct |
| 65 |
Correct |
242 ms |
27412 KB |
Output is correct |
| 66 |
Correct |
353 ms |
36248 KB |
Output is correct |
| 67 |
Correct |
99 ms |
27320 KB |
Output is correct |
| 68 |
Correct |
277 ms |
27548 KB |
Output is correct |
| 69 |
Correct |
245 ms |
27596 KB |
Output is correct |
| 70 |
Correct |
208 ms |
26848 KB |
Output is correct |
