Submission #1179366

#TimeUsernameProblemLanguageResultExecution timeMemory
1179366ema_nicoleRace (IOI11_race)C++17
0 / 100
8 ms11336 KiB
#include <iostream> #include <vector> #include <unordered_map> #include <map> using namespace std; const int NMAX = 200002; using ll = long long; 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] = 0; 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]; } weight[start]++; } int centroid = -1; void dfscentroid(int start, int sizee, int tot) { ///sizeul e de sus bool ok = 0; if(sizee > tot / 2) ok = 1; for(auto x : v[start]) { if(x.nod == parent[start] || f[x.nod]) continue; if(weight[x.nod] > n / 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, sizee + weight[start] - weight[x.nod], tot); } } unordered_map <ll, int> umap[NMAX]; int ans = INF; ///dist minima pt suma k void updateans(int start) { unordered_map <ll, int> lg; lg.clear(); if(umap[start].find(k) != umap[start].end()) ///dc deja e lant pana in el ans = min(ans, umap[start][k]); for(auto x : v[start]) { if(x.nod == parent[start]) continue; for(auto var : umap[x.nod]) { ///COMPARAM cu ce avem de la vechii fii if(lg.find(k - var.first - x.dist) != lg.end()) { ans = min(ans, lg[k - var.first - x.dist] + var.second + 1); } } for(auto var : umap[x.nod]) { ///UPDATAM if(var.first + x.dist > k) continue; if(lg.find(var.first + x.dist) != lg.end()) lg[var.first + x.dist] = min(lg[var.first + x.dist], var.second + 1); else lg[var.first + x.dist] = var.second + 1; } } } void dfsans(int start) { ///pt fiecare centroid, il conectam cu ce am avut bool ok = 0; for(auto x : v[start]) { if(x.nod == parent[start] || f[x.nod]) continue; dfsans(x.nod); ok = 1; for(auto var : umap[x.nod]) { ///updatam distantele din x.nod if(var.first + x.dist > k) continue; ///first = distanta, second = cate muchii if(umap[start].find(var.first + x.dist) != umap[start].end()) umap[start][var.first + x.dist] = min(umap[start][var.first + x.dist], var.second + 1); else umap[start][var.first + x.dist] = var.second + 1; } umap[start][x.dist] = 1; } if(!ok) ///frunza umap[start][0] = 0; if(start == centroid) ///doar pt CENTROID cautam dc exista drumuri de sum k updateans(centroid); for(auto x : v[start]) { ///stergem mapurile din fii ca nu ne mai pasa if(x.nod == parent[start]) continue; umap[x.nod].clear(); } /*cout << "NODUL " << start << '\n'; for(auto var : umap[start]) cout << var.first << " " << var.second << '\n';*/ } void build(int start) { ///de la subarborele lui start INCEPEM parent[start] = -1; dfssize(start); centroid = -1; dfscentroid(start, 0, weight[start]); parent[centroid] = -1; ///rebuild in subarborele nostru sizeurile de parinti etc dfssize(centroid); ///reindexam parintii basically dfsans(centroid); ///bifam pt el f[start] = 1; umap[centroid].clear(); for(auto x : v[start]) { ///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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...