Submission #1180060

#TimeUsernameProblemLanguageResultExecution timeMemory
1180060ema_nicoleRace (IOI11_race)C++17
Compilation error
0 ms0 KiB
#pragma GCC optimize ("Ofast", "unroll-loops") #include <iostream> #include <vector> #include <unordered_map> #include <map> using namespace std; const int NMAX = 200002; const int INF = 21e8; struct muchii { int nod, dist; }; vector <vector <muchii>> v; int n, k; bool f[NMAX]; ///dc deja am procesat ca centroid respectivul sau nu int parent[NMAX]; int weight[NMAX]; ///ce weight are subarb resp void dfssize(int start) { weight[start] = 1; for(auto x : v[start]) { if(x.nod == parent[start] || f[x.nod]) continue; parent[x.nod] = start; dfssize(x.nod); weight[start] += weight[x.nod]; } } int centroid = -1; void dfscentroid(int start, int tot) { ///sizeul e de sus bool ok = 0; if(tot - weight[start] > tot / 2) ok = 1; for(auto x : v[start]) { if(x.nod == parent[start] || f[x.nod]) continue; if(weight[x.nod] > tot / 2) ok = 1; } if(!ok) { ///am gasit centroidul centroid = start; return; } for(auto x : v[start]) { if(x.nod == parent[start] || f[x.nod]) continue; dfscentroid(x.nod, tot); } } map <int, int> umap, full; ///full pt centroid, umap pt fiul curent int ans = INF; ///dist minima pt suma k void updateans(int copil) { ///start e copilul, actually if(umap.find(k) != umap.end()) ///dc deja e lant pana in el ans = min(ans, umap[k]); for(auto var : umap) { ///ce val am pastrat in copil if(var.second > ans) continue; ///COMPARAM cu ce avem de la vechii fii if(full.find(k - var.first) != full.end()) ans = min(ans, full[k - var.first] + var.second); } for(auto var : umap) { ///UPDATAM if(var.first > k || var.second > ans) continue; if(full.find(var.first) != full.end()) full[var.first] = min(full[var.first], var.second); else full[var.first] = var.second; } } void dfsans(int start, int add, int muchii) { ///formam dist de la noduri la centroid if(muchii >= ans || add > k) ///deja e drum prea lung return; if(umap.find(add) != umap.end()) umap[add] = min(umap[add], muchii); else umap[add] = muchii; for(auto x : v[start]) { if(x.nod == parent[start] || f[x.nod]) continue; dfsans(x.nod, add + x.dist, muchii + 1); } } void build(int start) { ///de la subarborele lui start INCEPEM parent[start] = -1; dfssize(start); centroid = -1; dfscentroid(start, weight[start]); //cout << weight[start] << " "; parent[centroid] = -1; ///rebuild in subarborele nostru sizeurile de parinti etc dfssize(centroid); ///reindexam parintii basically full.clear(); for(auto x : v[centroid]) { if(f[x.nod]) continue; umap.clear(); dfsans(x.nod, x.dist, 1); ///formezi drumurile updateans(x.nod); ///unim fiul si si comparam } //cout << start << " " << centroid << " " << ans << '\n'; f[centroid] = 1; for(auto x : v[centroid]) { ///facem si in subarbori if(!f[x.nod]) build(x.nod); } } int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) { n = N, k = K; v.resize(n + 1); for(int i = 0; i < n - 1; i++) { v[h[i][0]].push_back({h[i][1], l[i]}); v[h[i][1]].push_back({h[i][0], l[i]}); } /*for(int i = 0; i < n; i++) { cout << "nodul " << i << '\n'; for(auto x : v[i]) cout << x.nod << " "; cout << '\n'; }*/ build(0); if(ans == INF) ans = -1; return ans; } int h[NMAX][2]; int l[NMAX]; int main() { int N, K; cin >> N >> K; for(int i = 0; i < N - 1; i++) cin >> h[i][0] >> h[i][1] >> l[i]; cout << best_path(N, K, h, l); return 0; }

Compilation message (stderr)

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