Submission #1264492

#TimeUsernameProblemLanguageResultExecution timeMemory
1264492ema_nicole경주 (Race) (IOI11_race)C++17
100 / 100
303 ms57336 KiB
#pragma GCC optimize ("Ofast", "unroll-loops") #include <iostream> #include <vector> #include <unordered_map> #include <map> using namespace std; const int NMAX = 2e5; const int INF = 1e9; using ll = long long; struct muchii { int nod, cost; }; vector <vector <muchii>> adj; int n, k; struct noduri{ int parent = -1; int weight = 1; ///al subarborelui int lant; ll dist = 0; ///de la 0 la nod int depth = 0; ///basically CATE muchii de la 0 la nod }v[NMAX + 2]; int cnt = 0; ///cate lanturi void dfsbuild(int start) { bool ok = 0; for(auto x : adj[start]) { if(x.nod == v[start].parent) continue; ok = 1; v[x.nod].parent = start; v[x.nod].dist = v[start].dist + x.cost; v[x.nod].depth = v[start].depth + 1; dfsbuild(x.nod); v[start].weight += v[x.nod].weight; } ///formam lanturile if(!ok) { ///frunza, lant nou cnt++; v[start].lant = cnt; return; } int maxx = 0, chain = 0; for(auto x : adj[start]) { if(x.nod == v[start].parent) continue; if(v[x.nod].weight > maxx) { maxx = v[x.nod].weight; chain = v[x.nod].lant; } } v[start].lant = chain; } vector <map <ll, int>> umap; ///pt fiec lant int ans = INF; void solve(int start) { for(auto x : adj[start]) { ///prima oara fiul heavy if(x.nod != v[start].parent && v[x.nod].lant == v[start].lant) { solve(x.nod); break; } } for(auto x : adj[start]) { if(x.nod == v[start].parent || v[x.nod].lant == v[start].lant) continue; solve(x.nod); ///Small to large guys if(umap[v[start].lant].size() < umap[v[x.nod].lant].size()) swap(umap[v[start].lant], umap[v[x.nod].lant]); ///Step 1) pt fiec fiu light, faci query cu lantul mare for(auto var : umap[v[x.nod].lant]) { ll caut = k + 2 * v[start].dist - var.first; if(umap[v[start].lant].find(caut) != umap[v[start].lant].end()) { ans = min(ans, var.second + umap[v[start].lant][caut] - 2 * v[start].depth); } } ///Step 2) pt fiec fiu light, adaugi in map-ul lantului mare for(auto var : umap[v[x.nod].lant]) { if(umap[v[start].lant].find(var.first) != umap[v[start].lant].end()) umap[v[start].lant][var.first] = min(umap[v[start].lant][var.first], var.second); else umap[v[start].lant][var.first] = var.second; } umap[v[x.nod].lant].clear(); } ///query ca lantul poate se termina in el if(umap[v[start].lant].find(v[start].dist + k) != umap[v[start].lant].end()) ans = min(ans, umap[v[start].lant][v[start].dist + k] - v[start].depth); ///la FINAL adaugam si nr nostru if(umap[v[start].lant].find(v[start].dist) != umap[v[start].lant].end()) umap[v[start].lant][v[start].dist] = min(umap[v[start].lant][v[start].dist], v[start].depth); else umap[v[start].lant][v[start].dist] = v[start].depth; } int best_path(int N, int K, int h[NMAX][2], int l[NMAX]) { n = N, k = K; adj.resize(n + 1); for(int i = 0; i < n - 1; i++) { adj[h[i][0]].push_back({h[i][1], l[i]}); adj[h[i][1]].push_back({h[i][0], l[i]}); } dfsbuild(0); /*for(int i = 0; i < n; i++) cout << v[i].parent << " " << v[i].weight << " " << v[i].lant << " " << v[i].dist << " " << v[i].depth << '\n';*/ umap.resize(cnt + 1); solve(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...