Submission #1003568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003568	2024-06-20T13:05:04 Z	ilef	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>
using namespace std;
const int inf=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[MAX_N];
bool subtree[MAX_N];
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]){
            subtree[node]+=treesize(child,node);
        }
    }
   // cout<<node<<" "<<subtree[node]<<endl;
    return subtree[node];
}
int findcentroid(int node,int parent,int treesz){
    for(auto[w,child]:graph[node]){
        if(child!=parent && !removed[child]&& treesize(child,node)>(treesz/2)){
           // 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)return;
    mx_depth=max(mx_depth,sum);
    if(filling)cnt[sum]=min(cnt[sum],depth+1);
    else{
        if(cnt[k-sum]<inf){
        ans=min(ans,depth+1+cnt[k-sum]);}
    }
    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){
  
    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);
            }
    }
   
    fill(cnt+1,cnt+mx_depth+1,inf);
    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.assign(n,vector<pair<int,int>>());
    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=inf;
    memset(cnt,inf,sizeof(cnt));
    memset(removed,false,sizeof(removed));
    centroid_decomp(0,0);
    //ans=cnt[k];
    return ans;
}/*
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}
int main()
{
  int ans;
  read_input();
 
  ans = best_path(N,K,H,L);
  /*for(int i=0;i<=K;i++){
      cout<<cnt[i]<<" ";
  }*/
  // cout<<findcentroid(0,0,n)<<endl;
  
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}

Compilation message

race.cpp:107:3: warning: "/*" within comment [-Wcomment]
  107 |   /*for(int i=0;i<=K;i++){
      |    
race.cpp:112:3: error: expected unqualified-id before 'if'
  112 |   if(ans==solution)
      |   ^~
race.cpp:114:3: error: expected unqualified-id before 'else'
  114 |   else
      |   ^~~~
race.cpp:117:3: error: expected unqualified-id before 'return'
  117 |   return 0;
      |   ^~~~~~
race.cpp:118:1: error: expected declaration before '}' token
  118 | }
      | ^