Submission #805304

#TimeUsernameProblemLanguageResultExecution timeMemory
805304KerimRace (IOI11_race)C++17
100 / 100
347 ms122516 KiB
#include "race.h" #include "bits/stdc++.h" #define ll long long using namespace std; typedef pair<int, int> pii; const int N = 2e5+5; const int INF = 1e9; vector<pii> adj[N]; int K, answer; int dp[N][105]; void dfs(int nd, int pr){ dp[nd][0] = 0; for (int i = 1; i <= K; i++) dp[nd][i] = INF; for (auto [c, e]: adj[nd]){ if (c == pr) continue; dfs(c, nd); //update answer for (int w1 = 0; w1 + e <= K; w1++){ int w2 = K - e - w1; answer = min(answer, dp[nd][w1] + dp[c][w2]+1); } //update dp for (int p = 0; p+e <= K; p++) dp[nd][p+e] = min(dp[nd][p+e],dp[c][p]+1); } } void dfs1(int nd, int pr, int lvl, ll weight){ if (weight == K) answer = min(answer, lvl); if (weight >= K) return; for (auto [c, e]: adj[nd]){ if (c == pr) continue; dfs1(c, nd, lvl+1, weight+e); } } map<ll, int> m[N]; void dfs2(int nd, int pr, ll W, int L){ m[nd].clear(); m[nd][W] = L; for (auto [c, e]: adj[nd]){ if (c == pr) continue; dfs2(c, nd, W+e, L+1); if (m[nd].size() < m[c].size()) swap(m[nd], m[c]); //update answer for (auto [w1, l1]: m[c]){ int w2 = K - w1 + 2*W; if (m[nd].find(w2) != m[nd].end()){ int l2 = m[nd][w2]; answer = min(answer, l1 + l2 - 2*L); } } //update map for (auto [w1, l1]: m[c]){ if (m[nd].find(w1) == m[nd].end()) m[nd][w1] = l1; else m[nd][w1] = min(m[nd][w1], l1); } m[c].clear(); } } int best_path(int n, int k, int H[][2], int L[]){ K = k; answer = INF; for (int i = 0; i < n - 1; i++){ int u = H[i][0], v = H[i][1], w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } if (k <= 100) //subtask 1 and 3 dfs(1, -1); else if(n <= 1000){ //subtask 2 for (int i = 0; i < n; i++) dfs1(i, -1, 0, 0); } else{ dfs2(1, -1, 0, 0); } if (answer == INF) answer = -1; return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...