제출 #709604

#제출 시각아이디문제언어결과실행 시간메모리
709604Ozy경주 (Race) (IOI11_race)C++17
0 / 100
3059 ms4948 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define pll pair<lli,lli> #define MAX 200000 #define des first #define d second vector<pll> hijos[MAX+2]; lli n,k,res,act,padre,mitad; //centroid lli tam[MAX+2],vis[MAX+2]; queue<lli> cola; bool cond; map<lli,lli> abso,rama; void dfs(lli pos, lli p) { tam[pos] = 1; for(auto h : hijos[pos]) { if (vis[h.des] == 1 || h.des == p) continue; dfs(h.des,pos); tam[pos] += tam[h.des]; } } void sub(lli pos, lli p,lli cam, lli sum) { //checa contra abso if (sum > k) return; lli a = k-sum; if (abso.find(a) != abso.end()) { a = abso[a] + cam; if (res == -1 || res > a) res = a; } //me meto a rama if (rama.find(sum) != rama.end()) rama[sum] = min(rama[sum],cam); else rama[sum] = cam; //sigo procesando el subarbol for(auto h : hijos[pos]) { if (h.des == padre || vis[h.des] == 1) continue; sub(h.des,pos,cam+1,sum+h.d); } } void solve(lli raiz) { abso.clear(); abso[0] = 0; for(auto h : hijos[raiz]) { if (vis[h.des] == 1) continue; rama.clear(); sub(h.des,raiz,1,h.d); if (rama.size() > abso.size()) swap(abso,rama); for (auto act : rama) { if (abso.find(act.first) != abso.end()) abso[act.first] = min(abso[act.first], act.second); else abso[act.first] = act.second; } } } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; res = -1; rep(i,0,n-2) { hijos[H[i][0]+1].push_back({H[i][1]+1, L[i]}); hijos[H[i][1]+1].push_back({H[i][0]+1, L[i]}); } cola.push(1); while(!cola.empty()){ act = cola.front(); cola.pop(); dfs(act,0); //obtengo el centroide mitad = tam[act]/2; padre = 0; do{ cond = false; for(auto h : hijos[act]) { if (h.des == padre || vis[h.des] == 1 || tam[h.des] <= mitad) continue; padre = act; act = h.des; cond = true; break; } }while(cond); solve(act); vis[act] = 1; for(auto h : hijos[act]) { if (vis[h.des] == 1) continue; cola.push(h.des); } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...