Submission #1322808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322808		hgia	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,k,ans=1e9;
int sz[N],h[N],dist[N];
bool del[N];
int best[1000005];
vector<pair<int,int>>d[N];
vector<int>used;
vector<pair<int,int>>neww;
void dfs(int u,int p)
{
  sz[u]=1;
  for(auto i:d[u])
  {
    int v=i.second;
    if(v==p||del[v])continue;
    dfs(v,u);
    sz[u]+=sz[v];
  }
}
int findroot(int u,int p,int n)
{
  for(auto i:d[u])
  {
    int v=i.second;
    if(v==p||del[v])continue;
    if(sz[v]>n/2)return findroot(v,u,n);
  }
  return u;
}
void caldist(int u,int p,int w)
{
  dist[u]=dist[p]+w;
  h[u]=h[p]+1;
  if(dist[u]>k)return;
  neww.push_back({dist[u],h[u]});
  used.push_back(dist[u]);
  ans=min(ans,h[u]+best[k-dist[u]]);
  for(auto i:d[u])
  {
    int v=i.second;
    w=i.first;
    if(v==p||del[v])continue;
    caldist(v,u,w);
  }
}
void updateans(int u)
{
  used.clear();
  for(auto i:d[u])
  {
    int v=i.second;
    int w=i.first;
    if(del[v])continue;
    neww.clear();
    caldist(v,u,w);
    for(auto tmp:neww)best[tmp.first]=min(best[tmp.first],tmp.second);
  }
  for(auto tmp:used)best[tmp]=1e9;
}
void solve(int u)
{
  dfs(u,0);
  int root=findroot(u,0,sz[u]);
  best[0]=0;
  h[root]=0;
  dist[root]=0;
  updateans(root);
  del[root]=true;
  for(auto i:d[root])
  {
    int v=i.second;
    if(del[v])continue;
    solve(v);
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>k;
  for(int i=1;i<n;i++)
  {
    int u ,v,w;
    cin>>u>>v>>w;
    u++;
    v++;
    d[u].push_back({w,v});
    d[v].push_back({w,u});
  }
  for(int i=1;i<=k;i++)best[i]=1e9;
  solve(1);
  if(ans==1e9)ans=-1;
  cout<<ans;
  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccA4RBbp.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccH4z0m2.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccA4RBbp.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status