Submission #1207968

#TimeUsernameProblemLanguageResultExecution timeMemory
1207968segfault_ikuyoRace (IOI11_race)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define pii pair<int,int> const int maxn=2*1e5+5; const int maxk=1e6+5; vector<pii> adj[maxn]; pii path[maxk]; int vis[maxn], siz[maxn]; int n,k,a,b,c; int ans; queue<pii> q; int dfssiz(int x, int pre){ int sizz=1; for(pii i:adj[x]){ if(i.first==pre||vis[i.first]) continue; sizz+=dfssiz(i.first,x); } siz[x]=sizz; //cout << x << '-' << siz[x] << '\n'; return sizz; } int dfsget(int x, int pre, int c){ for(pii i:adj[x]){ if(i.first==pre||vis[i.first]) continue; if(siz[i.first]>=siz[c]/2) { return dfsget(i.first,x,c); } } return x; } void dfssolve(int x, int pre, int d, int dd, int c){ if(dd>k) return; if(dd==k){ ans=min(ans,d); return; } if(path[k-dd].second==c){ ans=min(ans,path[k-dd].first+d); } for(pii i:adj[x]){ if(i.first==pre||vis[i.first]) continue; dfssolve(i.first,x,d+1,dd+i.second,c); } q.push({d,dd}); } int getcentroid(int x){ dfssiz(x,-1); return dfsget(x,-1,x); } void solve(int x){ if(vis[x]) return; int c=getcentroid(x); path[0]={0,c}; pii cur; for(pii i:adj[c]){ if(vis[i.first]) continue; //q.clear(); dfssolve(i.first,c,1,i.second,c); while(!q.empty()){ cur=q.front(); q.pop(); if(path[cur.second].second!=c) path[cur.second]={cur.first,c}; else path[cur.second].first=min(cur.first,path[cur.second].first); } } vis[c]=1; for(pii i:adj[c]){ if(vis[i.first]) continue; solve(i.first); } } signed main(){ cin.tie(0); ios_base::sync_with_stdio(0); memset(path,0xff,sizeof(path)); cin >> n >> k; ans=LLONG_MAX; for(int i=0;i<n-1;i++){ cin >> a >> b >> c; adj[a].pb({b,c}); adj[b].pb({a,c}); } solve(0); if(ans==LLONG_MAX) ans=-1; cout << ans << '\n'; return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccNuZNA4.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc0TPvmP.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccNuZNA4.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