# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1005524 |
2024-06-22T14:49:10 Z |
ilef |
Race (IOI11_race) |
C++14 |
|
222 ms |
34388 KB |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
//const int MAX_N=2e5+14;
#define KK 1000001
int n,k;
int ans;
int mx_depth;
int cnt[KK];
bool removed[MAXN];
int subtree[MAXN];
vector<pair<int,int>>graph[MAXN];
int treesize(int node,int parent){
subtree[node]=1;
for(auto [w,child]:graph[node]){
if(child!=parent && !removed[child]){
subtree[node]+=treesize(child,node);
}
}
return subtree[node];
}
int findcentroid(int node,int parent,int treesz){
int sz=treesz/2;
for(auto[w,child]:graph[node]){
if(child!=parent && !removed[child]&& subtree[child]>(sz)){
return findcentroid(child,node,treesz);
}
}
return node;
}
void getans(int sum,int node,int parent,int depth,bool filling){
if (sum>k){
return;
}
// mx_depth=max(mx_depth,sum);
if(filling==true){
if(cnt[sum]==-1)cnt[sum]=depth;
else{
cnt[sum]=min(cnt[sum],depth);}
}
else{
if(cnt[k-sum]!=-1){
if(ans==-1){
ans=depth+cnt[k-sum];
}
ans=min(ans,depth+cnt[k-sum]);
}
}
for(auto[w,child]:graph[node]){
if(child!=parent && ! removed[child]){
getans(sum+w,child,node,depth+1,filling);
}
}
}
void del(int sum,int node,int p=-1){
if(sum>k)return;
cnt[sum]=-1;
for(auto[w,child]:graph[node]){
if(!removed[child]&& child!=p){
del(sum+w,child,node);
}
}
}
void centroid_decomp(int node,int parent){
int centroid=findcentroid( node, parent,treesize(node,parent));
removed[centroid]=true;
cnt[0]=0;
for(auto &[w,child]:graph[centroid]){
if(!removed[child]){
getans(w,child,centroid,1,false);
getans(w,child,centroid,1,true);
}
}
//fill(cnt+1,cnt+mx_depth+1,inf);
for(auto[w,i]:graph[centroid]){
if(!removed[i]){
del(w,i);
}
}
for(auto[w,i]:graph[centroid]){
if(!removed[i]){
centroid_decomp(i,centroid);}
}
}
int best_path(int N,int K,int H[][2],int L[]){
mx_depth=0;
n=N;
k=K;
// graph.resize(n);
for(int i=0;i<n-1;i++){
int u=H[i][0];
int v=H[i][1];
int w=L[i];
graph[u].push_back({w,v});
graph[v].push_back({w,u});
}
ans=-1;
memset(cnt,-1,sizeof(cnt));
// memset(removed,false,sizeof(removed));
centroid_decomp(0,0);
// if(ans>=inf)ans=-1;
return ans;
}
Compilation message
race.cpp: In function 'int treesize(int, int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
15 | for(auto [w,child]:graph[node]){
| ^
race.cpp: In function 'int findcentroid(int, int, int)':
race.cpp:26:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for(auto[w,child]:graph[node]){
| ^
race.cpp: In function 'void getans(int, int, int, int, bool)':
race.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
52 | for(auto[w,child]:graph[node]){
| ^
race.cpp: In function 'void del(int, int, int)':
race.cpp:61:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto[w,child]:graph[node]){
| ^
race.cpp: In function 'void centroid_decomp(int, int)':
race.cpp:72:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for(auto &[w,child]:graph[centroid]){
| ^
race.cpp:80:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
80 | for(auto[w,i]:graph[centroid]){
| ^
race.cpp:85:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for(auto[w,i]:graph[centroid]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
13660 KB |
Output is correct |
2 |
Correct |
2 ms |
13660 KB |
Output is correct |
3 |
Correct |
2 ms |
13656 KB |
Output is correct |
4 |
Correct |
2 ms |
13660 KB |
Output is correct |
5 |
Correct |
1 ms |
13656 KB |
Output is correct |
6 |
Correct |
2 ms |
13660 KB |
Output is correct |
7 |
Correct |
2 ms |
13656 KB |
Output is correct |
8 |
Correct |
2 ms |
13660 KB |
Output is correct |
9 |
Correct |
2 ms |
13660 KB |
Output is correct |
10 |
Correct |
2 ms |
13452 KB |
Output is correct |
11 |
Correct |
2 ms |
13660 KB |
Output is correct |
12 |
Correct |
2 ms |
13680 KB |
Output is correct |
13 |
Correct |
2 ms |
13660 KB |
Output is correct |
14 |
Correct |
2 ms |
13676 KB |
Output is correct |
15 |
Correct |
1 ms |
13660 KB |
Output is correct |
16 |
Correct |
2 ms |
13660 KB |
Output is correct |
17 |
Correct |
2 ms |
13660 KB |
Output is correct |
18 |
Correct |
2 ms |
13660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
13660 KB |
Output is correct |
2 |
Correct |
2 ms |
13660 KB |
Output is correct |
3 |
Correct |
2 ms |
13656 KB |
Output is correct |
4 |
Correct |
2 ms |
13660 KB |
Output is correct |
5 |
Correct |
1 ms |
13656 KB |
Output is correct |
6 |
Correct |
2 ms |
13660 KB |
Output is correct |
7 |
Correct |
2 ms |
13656 KB |
Output is correct |
8 |
Correct |
2 ms |
13660 KB |
Output is correct |
9 |
Correct |
2 ms |
13660 KB |
Output is correct |
10 |
Correct |
2 ms |
13452 KB |
Output is correct |
11 |
Correct |
2 ms |
13660 KB |
Output is correct |
12 |
Correct |
2 ms |
13680 KB |
Output is correct |
13 |
Correct |
2 ms |
13660 KB |
Output is correct |
14 |
Correct |
2 ms |
13676 KB |
Output is correct |
15 |
Correct |
1 ms |
13660 KB |
Output is correct |
16 |
Correct |
2 ms |
13660 KB |
Output is correct |
17 |
Correct |
2 ms |
13660 KB |
Output is correct |
18 |
Correct |
2 ms |
13660 KB |
Output is correct |
19 |
Correct |
2 ms |
13660 KB |
Output is correct |
20 |
Correct |
2 ms |
13660 KB |
Output is correct |
21 |
Correct |
3 ms |
13660 KB |
Output is correct |
22 |
Correct |
2 ms |
13704 KB |
Output is correct |
23 |
Correct |
2 ms |
13660 KB |
Output is correct |
24 |
Correct |
2 ms |
13660 KB |
Output is correct |
25 |
Correct |
4 ms |
13660 KB |
Output is correct |
26 |
Correct |
3 ms |
13660 KB |
Output is correct |
27 |
Correct |
2 ms |
13524 KB |
Output is correct |
28 |
Correct |
2 ms |
13660 KB |
Output is correct |
29 |
Correct |
2 ms |
13660 KB |
Output is correct |
30 |
Correct |
2 ms |
13660 KB |
Output is correct |
31 |
Correct |
2 ms |
13660 KB |
Output is correct |
32 |
Correct |
2 ms |
13660 KB |
Output is correct |
33 |
Correct |
2 ms |
13660 KB |
Output is correct |
34 |
Correct |
2 ms |
13660 KB |
Output is correct |
35 |
Correct |
2 ms |
13660 KB |
Output is correct |
36 |
Correct |
2 ms |
13660 KB |
Output is correct |
37 |
Correct |
2 ms |
13660 KB |
Output is correct |
38 |
Correct |
2 ms |
13660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
13660 KB |
Output is correct |
2 |
Correct |
2 ms |
13660 KB |
Output is correct |
3 |
Correct |
2 ms |
13656 KB |
Output is correct |
4 |
Correct |
2 ms |
13660 KB |
Output is correct |
5 |
Correct |
1 ms |
13656 KB |
Output is correct |
6 |
Correct |
2 ms |
13660 KB |
Output is correct |
7 |
Correct |
2 ms |
13656 KB |
Output is correct |
8 |
Correct |
2 ms |
13660 KB |
Output is correct |
9 |
Correct |
2 ms |
13660 KB |
Output is correct |
10 |
Correct |
2 ms |
13452 KB |
Output is correct |
11 |
Correct |
2 ms |
13660 KB |
Output is correct |
12 |
Correct |
2 ms |
13680 KB |
Output is correct |
13 |
Correct |
2 ms |
13660 KB |
Output is correct |
14 |
Correct |
2 ms |
13676 KB |
Output is correct |
15 |
Correct |
1 ms |
13660 KB |
Output is correct |
16 |
Correct |
2 ms |
13660 KB |
Output is correct |
17 |
Correct |
2 ms |
13660 KB |
Output is correct |
18 |
Correct |
2 ms |
13660 KB |
Output is correct |
19 |
Correct |
77 ms |
19544 KB |
Output is correct |
20 |
Correct |
72 ms |
19536 KB |
Output is correct |
21 |
Correct |
83 ms |
19548 KB |
Output is correct |
22 |
Correct |
65 ms |
19540 KB |
Output is correct |
23 |
Correct |
39 ms |
19800 KB |
Output is correct |
24 |
Correct |
29 ms |
19544 KB |
Output is correct |
25 |
Correct |
74 ms |
22108 KB |
Output is correct |
26 |
Correct |
64 ms |
25180 KB |
Output is correct |
27 |
Correct |
82 ms |
23376 KB |
Output is correct |
28 |
Correct |
120 ms |
34388 KB |
Output is correct |
29 |
Correct |
124 ms |
33616 KB |
Output is correct |
30 |
Correct |
84 ms |
23380 KB |
Output is correct |
31 |
Correct |
75 ms |
23380 KB |
Output is correct |
32 |
Correct |
91 ms |
23416 KB |
Output is correct |
33 |
Correct |
109 ms |
22100 KB |
Output is correct |
34 |
Correct |
84 ms |
22096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
13660 KB |
Output is correct |
2 |
Correct |
2 ms |
13660 KB |
Output is correct |
3 |
Correct |
2 ms |
13656 KB |
Output is correct |
4 |
Correct |
2 ms |
13660 KB |
Output is correct |
5 |
Correct |
1 ms |
13656 KB |
Output is correct |
6 |
Correct |
2 ms |
13660 KB |
Output is correct |
7 |
Correct |
2 ms |
13656 KB |
Output is correct |
8 |
Correct |
2 ms |
13660 KB |
Output is correct |
9 |
Correct |
2 ms |
13660 KB |
Output is correct |
10 |
Correct |
2 ms |
13452 KB |
Output is correct |
11 |
Correct |
2 ms |
13660 KB |
Output is correct |
12 |
Correct |
2 ms |
13680 KB |
Output is correct |
13 |
Correct |
2 ms |
13660 KB |
Output is correct |
14 |
Correct |
2 ms |
13676 KB |
Output is correct |
15 |
Correct |
1 ms |
13660 KB |
Output is correct |
16 |
Correct |
2 ms |
13660 KB |
Output is correct |
17 |
Correct |
2 ms |
13660 KB |
Output is correct |
18 |
Correct |
2 ms |
13660 KB |
Output is correct |
19 |
Correct |
2 ms |
13660 KB |
Output is correct |
20 |
Correct |
2 ms |
13660 KB |
Output is correct |
21 |
Correct |
3 ms |
13660 KB |
Output is correct |
22 |
Correct |
2 ms |
13704 KB |
Output is correct |
23 |
Correct |
2 ms |
13660 KB |
Output is correct |
24 |
Correct |
2 ms |
13660 KB |
Output is correct |
25 |
Correct |
4 ms |
13660 KB |
Output is correct |
26 |
Correct |
3 ms |
13660 KB |
Output is correct |
27 |
Correct |
2 ms |
13524 KB |
Output is correct |
28 |
Correct |
2 ms |
13660 KB |
Output is correct |
29 |
Correct |
2 ms |
13660 KB |
Output is correct |
30 |
Correct |
2 ms |
13660 KB |
Output is correct |
31 |
Correct |
2 ms |
13660 KB |
Output is correct |
32 |
Correct |
2 ms |
13660 KB |
Output is correct |
33 |
Correct |
2 ms |
13660 KB |
Output is correct |
34 |
Correct |
2 ms |
13660 KB |
Output is correct |
35 |
Correct |
2 ms |
13660 KB |
Output is correct |
36 |
Correct |
2 ms |
13660 KB |
Output is correct |
37 |
Correct |
2 ms |
13660 KB |
Output is correct |
38 |
Correct |
2 ms |
13660 KB |
Output is correct |
39 |
Correct |
77 ms |
19544 KB |
Output is correct |
40 |
Correct |
72 ms |
19536 KB |
Output is correct |
41 |
Correct |
83 ms |
19548 KB |
Output is correct |
42 |
Correct |
65 ms |
19540 KB |
Output is correct |
43 |
Correct |
39 ms |
19800 KB |
Output is correct |
44 |
Correct |
29 ms |
19544 KB |
Output is correct |
45 |
Correct |
74 ms |
22108 KB |
Output is correct |
46 |
Correct |
64 ms |
25180 KB |
Output is correct |
47 |
Correct |
82 ms |
23376 KB |
Output is correct |
48 |
Correct |
120 ms |
34388 KB |
Output is correct |
49 |
Correct |
124 ms |
33616 KB |
Output is correct |
50 |
Correct |
84 ms |
23380 KB |
Output is correct |
51 |
Correct |
75 ms |
23380 KB |
Output is correct |
52 |
Correct |
91 ms |
23416 KB |
Output is correct |
53 |
Correct |
109 ms |
22100 KB |
Output is correct |
54 |
Correct |
84 ms |
22096 KB |
Output is correct |
55 |
Correct |
7 ms |
13912 KB |
Output is correct |
56 |
Correct |
8 ms |
13916 KB |
Output is correct |
57 |
Correct |
47 ms |
19816 KB |
Output is correct |
58 |
Correct |
21 ms |
19832 KB |
Output is correct |
59 |
Correct |
67 ms |
25216 KB |
Output is correct |
60 |
Correct |
222 ms |
33908 KB |
Output is correct |
61 |
Correct |
93 ms |
24916 KB |
Output is correct |
62 |
Correct |
102 ms |
25556 KB |
Output is correct |
63 |
Correct |
121 ms |
25456 KB |
Output is correct |
64 |
Correct |
198 ms |
24148 KB |
Output is correct |
65 |
Correct |
75 ms |
26448 KB |
Output is correct |
66 |
Correct |
176 ms |
31568 KB |
Output is correct |
67 |
Correct |
53 ms |
26820 KB |
Output is correct |
68 |
Correct |
117 ms |
25940 KB |
Output is correct |
69 |
Correct |
104 ms |
23704 KB |
Output is correct |
70 |
Correct |
104 ms |
25940 KB |
Output is correct |