제출 #260287

#제출 시각아이디문제언어결과실행 시간메모리
260287aggu_01000101경주 (Race) (IOI11_race)C++14
컴파일 에러
0 ms0 KiB
#include <iostream> #include <assert.h> #include <algorithm> #include <vector> #include <set> #include <string> #include <queue> #include <map> #include <bits/stdc++.h> #define initrand mt19937 mt_rand(time(0)); #define rand mt_rand() #define int long long #define INF 10000000000000000 #define MOD 1000000007 using namespace std; const int N = 200005; const int K = 1000005; vector<pair<int, int>> adj[N]; int tb = 0; int t = 0; int tin[N], tout[N]; int depth[N], edges[N]; int h[N][20]; int s[N], size = 0; int ans = INF; vector<int> ett; map<int, int> d; map<int, bool> vis; int LCA_DFS(int i, int par, int dep, int edep){ tin[i] = ett.size(); ett.push_back(i); depth[i] = dep; edges[i] = edep; s[i] = 1; if(i!=par){ h[i][0] = par; for(int j = 1;j<=19;j++){ if(h[i][j-1] != -1) h[i][j] = h[h[i][j-1]][j-1]; } } for(pair<int, int> j: adj[i]){ if(j.first == par) continue; s[i] += LCA_DFS(j.first, i, dep + j.second, edep+1); } tout[i] = ett.size(); return s[i]; } bool anc(int u, int v){ if((tin[u] <= tin[v]) && (tout[u] >= tout[v])) return true; return false; } int LCA(int u, int v){ if(anc(u, v)){ return u; } if(anc(v, u)) return v; for(int i = 19;i>=0;i--){ if(h[u][i]!=-1 && !anc(h[u][i], v)) u = h[u][i]; } return h[u][0]; } pair<int, int> dist(int u, int v){ return {(depth[u] + depth[v] - 2*depth[LCA(u, v)]), (edges[u] + edges[v] - 2*edges[LCA(u, v)])}; } pair<int, int> dfs(int i, int par, int keep){ pair<int, int> comp = {0, 0}; int bigChild = -1, mx = 0; for(pair<int, int> j: adj[i]){ if(j.first == par) continue; if(s[j.first] > mx){ bigChild = j.first; mx = s[j.first]; } } for(pair<int, int> j: adj[i]){ if(j.first == par || j.first == bigChild) continue; dfs(j.first, i, 0); } if(bigChild != -1){ comp = dfs(bigChild, i, 1); comp.first += dist(bigChild, i).first; //d[x] is actually at d[x - comp.first] //when we want d[x], we have to try d[x + ] comp.second++;//d[x] = y actually means d[x] = y + comp.second } vis[0 - comp.first] = true; d[0 - comp.first] = -comp.second; if(vis[tb - comp.first]) ans = min(ans, d[tb-comp.first] + comp.second); for(pair<int, int> j: adj[i]){ if(j.first == par || j.first == bigChild) continue; for(int x = tin[j.first];x<tout[j.first];x++){ pair<int, int> lol = dist(i, ett[x]); if(lol.first > tb) continue; if(vis[tb - lol.first - comp.first]) ans = min(ans, d[tb-lol.first-comp.first] + comp.second + lol.second); } for(int x = tin[j.first];x<tout[j.first];x++){ pair<int, int> lol = dist(i, ett[x]); if(lol.first > tb) continue; if(!vis[lol.first - comp.first]){ vis[lol.first - comp.first] = true; d[lol.first - comp.first] = lol.second - comp.second; } else{ d[lol.first - comp.first] = min(d[lol.first - comp.first], lol.second - comp.second); } } } if(keep == 0){ d.clear(); vis.clear(); } return comp; } signed best_path(signed n, signed k, signed hh[][2], signed l[]){ tb = k; ans = INF; for(int i = 0;i<(n-1);i++){ adj[hh[i][0]+1].push_back({hh[i][1]+1, l[i]}); adj[hh[i][1]+1].push_back({hh[i][0]+1, l[i]}); } for(int i = 1;i<=n;i++){ for(int j = 0;j<20;j++) h[i][j] = -1; } LCA_DFS(1, 1, 0, 0); dfs(1 ,1 ,0); if(ans>=INF) ans = -1; return ans; } signed main(){ signed n, k; cin>>n>>k; signed bitch[n-1][2]; signed l[n-1]; for(int i =0 ;i<(n-1);i++) cin>>bitch[i][0]>>bitch[i][1]>>l[i]; cout<<best_path(n, k, bitch, l)<<endl; } /* 11 12 0 1 3 0 2 4 2 3 5 3 4 4 4 5 6 0 6 3 6 7 2 6 8 5 8 9 6 8 10 7 */ /* 3 3 0 1 1 1 2 1 */

컴파일 시 표준 에러 (stderr) 메시지

/tmp/ccKodaxe.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccwbjBZd.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status