Submission #1179348

#TimeUsernameProblemLanguageResultExecution timeMemory
1179348ema_nicoleRace (IOI11_race)C++17
0 / 100
5 ms9800 KiB
#include <iostream> #include <vector> #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; 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]) continue; parent[x.nod] = start; dfssize(x.nod); weight[start] += weight[x.nod]; } weight[start]++; } int centroid = -1; void dfscentroid(int start, int sizee) { ///sizeul e de sus bool ok = 0; if(sizee > n / 2) ok = 1; for(auto x : v[start]) { if(x.nod == parent[start]) 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]) continue; dfscentroid(x.nod, sizee + weight[start] - weight[x.nod]); } } map <ll, int> umap[NMAX]; int ans = INF; ///dist minima pt suma k void updateans(int start) { 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 - k] + var.second + 1); } for(auto var : umap[x.nod]) { ///UPDATAM 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) { bool ok = 0; for(auto x : v[start]) { if(x.nod == parent[start]) continue; dfsans(x.nod); ok = 1; for(auto var : umap[x.nod]) { ///updatam distantele din x.nod ///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; else ///cautam dc exista drumuri de suma k updateans(start); /*cout << "NODUL " << start << '\n'; for(auto var : umap[start]) cout << var.first << " " << var.second << '\n';*/ } 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'; }*/ parent[0] = -1; dfssize(0); /*for(int i = 0; i < n; i++) cout << weight[i] << " "; cout << '\n';*/ dfscentroid(0, 0); parent[centroid] = -1; dfssize(0); ///reindexam parintii dfsans(centroid); 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]; for(int i = 0; i < N - 1; i++) cin >> l[i]; cout << best_path(N, K, h, l); return 0; }*/ /* 11 12 0 1 0 2 2 3 3 4 4 5 0 6 6 7 6 8 8 9 8 10 3 4 5 4 6 3 2 5 6 7 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...