| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1022558 |
2024-07-13T17:42:23 Z |
socpite |
Race (IOI11_race) |
C++14 |
|
352 ms |
59220 KB |
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5;
map<long long, int> mp;
int sz[maxn];
int dep1[maxn];
long long dep2[maxn];
vector<pair<int, int>> g[maxn];
void add(long long val, int dep){
if(mp.find(val) != mp.end())mp[val] = min(mp[val], dep);
else mp[val] = dep;
}
int query(long long val){
if(mp.find(val) == mp.end())return maxn;
else return mp[val];
}
// k = dep[a] + dep[b] - 2*dep[lca] => dep[b] = k - dep[a] + 2*dep[lca];
void pre_dfs(int x, int p){
sz[x] = 1;
for(auto v: g[x]){
if(v.first == p)continue;
dep1[v.first] = dep1[x] + 1;
dep2[v.first] = dep2[x] + v.second;
pre_dfs(v.first, x);
sz[x] += sz[v.first];
}
}
int dfs_query(int x, int p, long long coeff){
int re = query(coeff - dep2[x]) + dep1[x];
for(auto v: g[x]){
if(v.first == p)continue;
re = min(re, dfs_query(v.first, x, coeff));
}
return re;
}
void dfs_add(int x, int p){
add(dep2[x], dep1[x]);
for(auto v: g[x]){
if(v.first == p)continue;
dfs_add(v.first, x);
}
}
int dfs(int x, int p, int k){
sz[x] = 1;
int ans = maxn, bg = -1;
for(auto v: g[x]){
if(v.first == p)continue;
if(bg == -1 || sz[bg] < sz[v.first])bg = v.first;
}
for(auto v: g[x]){
if(v.first == p || v.first == bg)continue;
ans = min(ans, dfs(v.first, x, k));
mp.clear();
}
if(bg != -1)ans = min(ans, dfs(bg, x, k));
for(auto v: g[x]){
if(v.first == p || v.first == bg)continue;
ans = min(ans, dfs_query(v.first, x, 2*dep2[x] + k) - 2*dep1[x]);
dfs_add(v.first, x);
}
ans = min(ans, query(dep2[x] + k) - dep1[x]);
add(dep2[x], dep1[x]);
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
mp.clear();
dep1[0] = 0;
dep2[0] = 0;
for(int i = 0; i < N; i++)g[i].clear();
for(int i = 0; i < N-1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
pre_dfs(0, -1);
int ans = dfs(0, -1, K);
return ans > N ? -1 : ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 5 |
Correct |
3 ms |
11472 KB |
Output is correct |
| 6 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 8 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 9 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 11 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 12 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 14 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 15 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 17 |
Correct |
4 ms |
15196 KB |
Output is correct |
| 18 |
Correct |
2 ms |
11356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 5 |
Correct |
3 ms |
11472 KB |
Output is correct |
| 6 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 8 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 9 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 11 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 12 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 14 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 15 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 17 |
Correct |
4 ms |
15196 KB |
Output is correct |
| 18 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 19 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 20 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 21 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 22 |
Correct |
4 ms |
11608 KB |
Output is correct |
| 23 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 24 |
Correct |
4 ms |
11448 KB |
Output is correct |
| 25 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 26 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 27 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 28 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 29 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 30 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 31 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 32 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 33 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 34 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 35 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 36 |
Correct |
4 ms |
11444 KB |
Output is correct |
| 37 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 38 |
Correct |
4 ms |
11356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 5 |
Correct |
3 ms |
11472 KB |
Output is correct |
| 6 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 8 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 9 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 11 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 12 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 14 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 15 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 17 |
Correct |
4 ms |
15196 KB |
Output is correct |
| 18 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 19 |
Correct |
97 ms |
17968 KB |
Output is correct |
| 20 |
Correct |
94 ms |
18868 KB |
Output is correct |
| 21 |
Correct |
97 ms |
18592 KB |
Output is correct |
| 22 |
Correct |
87 ms |
19272 KB |
Output is correct |
| 23 |
Correct |
140 ms |
19540 KB |
Output is correct |
| 24 |
Correct |
80 ms |
19280 KB |
Output is correct |
| 25 |
Correct |
54 ms |
24400 KB |
Output is correct |
| 26 |
Correct |
36 ms |
28876 KB |
Output is correct |
| 27 |
Correct |
109 ms |
26232 KB |
Output is correct |
| 28 |
Correct |
159 ms |
59220 KB |
Output is correct |
| 29 |
Correct |
161 ms |
57672 KB |
Output is correct |
| 30 |
Correct |
141 ms |
26620 KB |
Output is correct |
| 31 |
Correct |
119 ms |
26704 KB |
Output is correct |
| 32 |
Correct |
130 ms |
26708 KB |
Output is correct |
| 33 |
Correct |
152 ms |
25680 KB |
Output is correct |
| 34 |
Correct |
250 ms |
38236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 2 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 4 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 5 |
Correct |
3 ms |
11472 KB |
Output is correct |
| 6 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 7 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 8 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 9 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 10 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 11 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 12 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 14 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 15 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 17 |
Correct |
4 ms |
15196 KB |
Output is correct |
| 18 |
Correct |
2 ms |
11356 KB |
Output is correct |
| 19 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 20 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 21 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 22 |
Correct |
4 ms |
11608 KB |
Output is correct |
| 23 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 24 |
Correct |
4 ms |
11448 KB |
Output is correct |
| 25 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 26 |
Correct |
5 ms |
11356 KB |
Output is correct |
| 27 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 28 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 29 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 30 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 31 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 32 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 33 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 34 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 35 |
Correct |
3 ms |
11356 KB |
Output is correct |
| 36 |
Correct |
4 ms |
11444 KB |
Output is correct |
| 37 |
Correct |
4 ms |
11352 KB |
Output is correct |
| 38 |
Correct |
4 ms |
11356 KB |
Output is correct |
| 39 |
Correct |
97 ms |
17968 KB |
Output is correct |
| 40 |
Correct |
94 ms |
18868 KB |
Output is correct |
| 41 |
Correct |
97 ms |
18592 KB |
Output is correct |
| 42 |
Correct |
87 ms |
19272 KB |
Output is correct |
| 43 |
Correct |
140 ms |
19540 KB |
Output is correct |
| 44 |
Correct |
80 ms |
19280 KB |
Output is correct |
| 45 |
Correct |
54 ms |
24400 KB |
Output is correct |
| 46 |
Correct |
36 ms |
28876 KB |
Output is correct |
| 47 |
Correct |
109 ms |
26232 KB |
Output is correct |
| 48 |
Correct |
159 ms |
59220 KB |
Output is correct |
| 49 |
Correct |
161 ms |
57672 KB |
Output is correct |
| 50 |
Correct |
141 ms |
26620 KB |
Output is correct |
| 51 |
Correct |
119 ms |
26704 KB |
Output is correct |
| 52 |
Correct |
130 ms |
26708 KB |
Output is correct |
| 53 |
Correct |
152 ms |
25680 KB |
Output is correct |
| 54 |
Correct |
250 ms |
38236 KB |
Output is correct |
| 55 |
Correct |
15 ms |
12376 KB |
Output is correct |
| 56 |
Correct |
9 ms |
11868 KB |
Output is correct |
| 57 |
Correct |
59 ms |
18136 KB |
Output is correct |
| 58 |
Correct |
32 ms |
19148 KB |
Output is correct |
| 59 |
Correct |
63 ms |
35188 KB |
Output is correct |
| 60 |
Correct |
141 ms |
58192 KB |
Output is correct |
| 61 |
Correct |
142 ms |
27728 KB |
Output is correct |
| 62 |
Correct |
107 ms |
26612 KB |
Output is correct |
| 63 |
Correct |
147 ms |
26664 KB |
Output is correct |
| 64 |
Correct |
352 ms |
31316 KB |
Output is correct |
| 65 |
Correct |
333 ms |
39748 KB |
Output is correct |
| 66 |
Correct |
155 ms |
52244 KB |
Output is correct |
| 67 |
Correct |
73 ms |
28100 KB |
Output is correct |
| 68 |
Correct |
197 ms |
37460 KB |
Output is correct |
| 69 |
Correct |
198 ms |
35428 KB |
Output is correct |
| 70 |
Correct |
192 ms |
36688 KB |
Output is correct |
