Submission #1043983

#TimeUsernameProblemLanguageResultExecution timeMemory
1043983dwuyRace (IOI11_race)C++14
Compilation error
0 ms0 KiB
#include "race.h" #include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int, int> pii; struct Map{ int sz, id; vector<int> vis; vector<int> val; Map(int n){ this->sz = n; this->id = 1; this->vis.assign(n + 5, 0); this->val.assign(n + 5, 0); } void clear(){ id++; } void add(int key, int val){ this->vis[key] = id; this->val[key] = val; } int get(int key){ return this->vis[key] == id? this->val[key] : 1e9; } }; const int MX = 200005; int n, k, ans = MX; int numC[MX]; bitset<MX> vist; vector<pii> G[MX]; void calChild(int u, int p){ numC[u] = 1; for(pii &tmp: G[u]){ int v, c; tie(v, c) = tmp; if(v==p || vist[v]) continue; calChild(v, u); numC[u] += numC[v]; } } int Centroid(int u, int p, const int &half){ for(pii &tmp: G[u]){ int v = tmp.fi; if(v == p || vist[v]) continue; if(numC[v] > half) return Centroid(v, u, half); } return u; } int dis[MX]; int node[MX]; Map mp(1000005); int calValue(int u){ mp.clear(); int res = MX; mp.add(0, 1); for(pii &tmp: G[u]){ int v, c; tie(v, c) = tmp; if (vist[v]) continue; vector<int> path; stack<pii> Q; Q.push({v, u}); node[v] = 2; dis[v] = c; while(Q.size()){ int u, p; tie(u, p) = Q.top(); Q.pop(); path.push_back(u); for(pii &tmp: G[u]){ int v, c; tie(v, c) = tmp; if(vist[v] || v == p) continue; Q.push({v, u}); dis[v] = dis[u] + c; node[v] = node[u] + 1; } } for(int vt: path) if(dis[vt]<=k){ int gm = mp.get(k - dis[vt]); if(gm) res = min(res, gm + node[vt] - 1); } for(int vt: path) if(dis[vt]<=k){ mp.add(dis[vt], min(mp.get(dis[vt]), node[vt])); } } return res; } void buon(int u){ calChild(u, 0); u = Centroid(u, 0, numC[u]>>1); ans = min(ans, calValue(u)); vist[u] = 1; for(pii &tmp: G[u]){ int v = tmp.fi; if(!vist[v]) buon(v); } } int best_path(int N, int K, int H[][2], int L[]){ n = N; k = K; for(int i=0; i<n-1; i++){ int u = H[i][0]; int v = H[i][1]; int c = L[i]; u++, v++; G[u].push_back({v, c}); G[v].push_back({u, c}); } buon(1); return ans==MX? -1 : ans - 1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int N, K; cin >> N >> K; int H[N][2]; int L[N]; for(int i=0; i<N-1; i++){ cin >> H[i][0] >> H[i][1] >> L[i]; H[i][0]--, H[i][1]--; } cout << best_path(N, K, H, L); return 0; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc1AeZu3.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccG4dHf3.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status