Submission #1197412

#TimeUsernameProblemLanguageResultExecution timeMemory
119741244100Race (IOI11_race)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define pub push_back #define fi first #define se second using namespace std; typedef long long ll; const int MaxN=2e5+5,MaxK=1e6+5; int N,K,ans,timer=1; int sz[MaxN],del[MaxN],ach[MaxK],min_e[MaxK]; vector<pair<int,int>> adj[MaxN]; void DFS(int u,int pre) { int i,j; sz[u]=1; for(auto x:adj[u]) { int v=x.fi; if(v!=pre && !del[v]) { DFS(v,u); sz[u]+=sz[v]; } } } int Cen(int u,int pre,int Size) { for(auto x:adj[u]) { int v=x.fi; if(v!=pre && sz[v]>Size/2 && !del[v]) return Cen(v,u,Size); } return u; } void calc(int u,int pre,int dist,int edges,bool check) { if(dist>K) return; if(check) { if(ach[dist]!=timer || edges<min_e[dist]) { ach[dist]=timer; min_e[dist]=edges; } } else { if(dist<=K && ach[K-dist]==timer) { int Sum_e=edges+min_e[K-dist]; if(ans==-1 || Sum_e<ans) ans=Sum_e; } if(dist==K) { if(ans==-1 || edges<ans) ans=edges; } } for(auto x:adj[u]) { int v=x.fi; int w=x.se; if(v!=pre && !del[v]) calc(v,u,dist+w,edges+1,check); } } void Dec(int u) { DFS(u,-1); int cen,i,j,k,v,w; cen=Cen(u,0,sz[u]); del[cen]=1; ++timer; ach[0]=timer; min_e[0]=0; for(auto x:adj[cen]) { v=x.fi; w=x.se; if(!del[v]) { calc(v,cen,w,1,0); calc(v,cen,w,1,1); } } for(auto x:adj[cen]) { v=x.fi; if(!del[v]) Dec(v); } } int best_path(int N,int K,int H[][2],int L[]) { ans=-1; memset(del,0,sizeof(del)); int i,j; for(i=0;i<N;++i) adj[i].clear(); for(i=0;i<N-1;++i) { adj[H[i][0]].pub({H[i][1],L[i]}); adj[H[i][1]].pub({H[i][0],L[i]}); } Dec(0); return ans; } int main() { ios_base::sync_with_stdio(0); int i,j,res; scanf("%d%d",&N,&K); int H[MaxN][2],L[MaxN]; for(i=0;i<N-1;++i) scanf("%d%d%d",&H[i][0],&H[i][1],&L[i]); res=best_path(N,K,H,L); printf("%d",res); return 0; }

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d%d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~
race.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%d%d%d",&H[i][0],&H[i][1],&L[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccDOdqN8.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqWjQZn.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status