Submission #1118474

#TimeUsernameProblemLanguageResultExecution timeMemory
1118474alexddRace (IOI11_race)C++17
43 / 100
3085 ms132448 KiB
#include "race.h" #include<bits/stdc++.h> using namespace std; const int INF = 1e8; int rez; long long K; vector<pair<int,int>> con[200005]; map<long long,int> dp[200005]; int d[200005]; long long d2[200005]; void dfs(int nod, int par) { if(d2[nod]==K) rez = min(rez, d[nod]); int maxc=-1,heavy=-1; for(auto [adj,w]:con[nod]) { if(adj==par) continue; d[adj] = d[nod] + 1; d2[adj] = d2[nod] + w; dfs(adj,nod); if((int)dp[adj].size() > maxc) maxc = dp[adj].size(), heavy=adj; } if(heavy==-1) { } else { swap(dp[nod], dp[heavy]); for(auto [adj,w]:con[nod]) { if(adj==par || adj==heavy) continue; for(auto it:dp[adj]) { rez = min(rez, it.second + dp[nod][K+2*d2[nod]-it.first] + 2*INF - 2*d[nod]); ///it.first + x - 2*d2[nod] = K } for(auto it:dp[adj]) if(it.first - d2[nod] <= K) dp[nod][it.first] = min(dp[nod][it.first], it.second); dp[adj].clear(); } } rez = min(rez, dp[nod][K+d2[nod]] + INF - d[nod]); ///x - d2[nod] = K dp[nod][d2[nod]] = min(dp[nod][d2[nod]], d[nod] - INF); } int best_path(int N, int copK, int H[][2], int L[]) { K = copK; rez = N+2; for(int i=0;i<N-1;i++) { con[H[i][0]].push_back({H[i][1],L[i]}); con[H[i][1]].push_back({H[i][0],L[i]}); } dfs(0,-1); if(rez==N+2) rez=-1; return rez; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...