| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003596 |
2024-06-20T13:45:36 Z |
ilef |
Race (IOI11_race) |
C++14 |
|
2 ms |
4444 KB |
#include <bits/stdc++.h>
using namespace std;
const int inf=2e5+14;
const int MAXN=2e5+14;
//const int MAX_N=2e5+14;
const int KK=1e6+1;
int n,k;
int ans;
int mx_depth;
int cnt[KK];
bool removed[MAXN];
int subtree[MAXN];
vector<vector<pair<int,int>>>graph;
int treesize(int node,int parent){
subtree[node]=1;
for(auto [w,child]:graph[node]){
if(child!=parent && !removed[child]){
// cout<<child<<endl;
subtree[node]+=treesize(child,node);
}
}
// cout<<node<<" "<<subtree[node]<<endl;
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]&& treesize(child,node)>(sz)){
// cout<<child<<" "<<node<<" "<<treesize(child,node)<<" "<<treesz<<endl;
return findcentroid(child,node,treesz);
}
}
return node;
}
void getans(int sum,int node,int parent,int depth,bool filling){
if (sum>k){
// cout<<k<<" "<<111<<endl;
// cout<<sum<<endl;
return;
}
mx_depth=max(mx_depth,sum);
if(filling==true){
cnt[sum]=min(cnt[sum],depth);
// cout<<sum<<" "<<depth<<" "<<node<<" "<<parent<<endl;
}
else{
if(cnt[k-sum]!=inf){
ans=min(ans,depth+cnt[k-sum]);
cnt[k]=min(cnt[k],ans);
}
}
for(auto[w,child]:graph[node]){
if(child!=parent && ! removed[child]){
getans(sum+w,child,node,depth+1,filling);
}
}
}
void centroid_decomp(int node,int parent){
fill(cnt+1,cnt+mx_depth+1,inf);
int centroid=findcentroid( node, parent,treesize(node,parent));
// cout<<endl<<endl;
// cout<<centroid<<endl;
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);
// cout<<centroid<<" "<<child<<endl;
}
}
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;
// cout<<k<<endl;
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});
//cout<<u<<" "<<v<<" "<<w<<endl;
}
ans=inf;
memset(cnt,inf,sizeof(cnt));
memset(removed,false,sizeof(removed));
centroid_decomp(0,0);
// cout<<findcentroid(0,0,n)<<endl;
// cout<<treesize(0,0)<<endl;
//ans=cnt[k];
return ans;
}
Compilation message
race.cpp: In function 'int treesize(int, int)':
race.cpp:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
16 | for(auto [w,child]:graph[node]){
| ^
race.cpp: In function 'int findcentroid(int, int, int)':
race.cpp:27:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
27 | for(auto[w,child]:graph[node]){
| ^
race.cpp: In function 'void getans(int, int, int, int, bool)':
race.cpp:54:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for(auto[w,child]:graph[node]){
| ^
race.cpp: In function 'void centroid_decomp(int, int)':
race.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for(auto &[w,child]:graph[centroid]){
| ^
race.cpp:76:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | for(auto[w,i]:graph[centroid]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
