Submission #1247926

#TimeUsernameProblemLanguageResultExecution timeMemory
1247926nekolieDreaming (IOI13_dreaming)C++20
0 / 100
28 ms12352 KiB
// Fluixarata or Cyngulini? // That is the question... #include "dreaming.h" #include <bits/stdc++.h> using namespace std; void dfs(int v, int p, int dp[], bool odw[], vector<pair<int,int>> tree[], int &maks) { dp[v] = 0, odw[v] = true; int x = 0, y = 0; for (auto [u,w] : tree[v]) { if (u == p) continue; dfs(u,v,dp,odw,tree,maks), dp[v] = max(dp[v],dp[u]+w); if (dp[u]+w > x) y = x, x = dp[u]+w; else if (dp[u]+w > y) y = dp[u]+w; } maks = max(maks,x+y); } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { bool odw[n+1]; fill(odw,odw+n+1,false); int dp[n+1], inf = (1<<30), x = -inf, y = -inf, z = -inf; vector<pair<int,int>> tree[n+1]; 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,dp,odw,tree,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({x,(x+1)/2+(y+1)/2+l,(y+1)/2+(z+1)/2+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...