Submission #1247949

#TimeUsernameProblemLanguageResultExecution timeMemory
1247949nekolieDreaming (IOI13_dreaming)C++20
100 / 100
67 ms16968 KiB
// Fluixarata or Cyngulini? // That is the question... #include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int maxn = 100001, inf = (1<<30); int dp[maxn][2], odp; bool odw[maxn]; vector<pair<int,int>> tree[maxn]; void dfs(int v, int p) { odw[v] = true; int x = 0, y = 0; for (auto [u,w] : tree[v]) { if (u == p) continue; dfs(u,v), dp[v][0] = max(dp[v][0],dp[u][0]+w); if (dp[u][0]+w > x) y = x, x = dp[u][0]+w; else if (dp[u][0]+w > y) y = dp[u][0]+w; } odp = max(odp,x+y); } void dfs2(int v, int p, int &maks) { int opt = -inf; maks = min(maks,max(dp[v][0],dp[v][1])); for (auto [u,w] : tree[v]) if (u != p) dp[u][1] = max(dp[v][1],opt)+w, opt = max(opt,dp[u][0]+w); reverse(tree[v].begin(),tree[v].end()), opt = -inf; for (auto [u,w] : tree[v]) if (u != p) dp[u][1] = max(dp[u][1],opt+w), opt = max(opt,dp[u][0]+w), dfs2(u,v,maks); } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { int x = -inf, y = -inf, z = -inf; for (int i = 0; i < m; i++) tree[A[i]+1].push_back({B[i]+1,T[i]}), tree[B[i]+1].push_back({A[i]+1,T[i]}); for (int i = 1; i <= n; i++) { if (odw[i]) continue; int maks = inf; dfs(i,0), dfs2(i,0,maks); if (maks > x) z = y, y = x, x = maks; else if (maks > y) z = y, y = maks; else if (maks > z) z = maks; } return max({odp,x+y+l,y+z+2*l}); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...