Submission #1199322

#TimeUsernameProblemLanguageResultExecution timeMemory
1199322Hamed_GhaffariDreaming (IOI13_dreaming)C++20
100 / 100
48 ms15820 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define SZ(x) int(x.size()) const int MXN = 1e5+5; vector<pii> g[MXN]; int dp[MXN]; bool vis[MXN]; vector<int> vec; void dfs(int v, int p=-1) { vis[v] = 1; vec.push_back(v); for(auto [u, w] : g[v]) if(u != p) { dfs(u, v); dp[v] = max(dp[v], dp[u]+w); } } void reroot(int v, int p=-1) { int mx1 = 0, mx2 = -1e9; for(auto [u, w] : g[v]) { int val = dp[u] + w; if(val>mx2) mx2=val; if(mx2>mx1) swap(mx1, mx2); } for(auto [u, w] : g[v]) if(u!=p) { int val = dp[u] + w; dp[v] = val==mx1 ? mx2 : mx1; reroot(u, v); } dp[v] = mx1; } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { for(int i=0; i<m; i++) { g[A[i]].push_back({B[i], T[i]}); g[B[i]].push_back({A[i], T[i]}); } vector<int> diams; for(int i=0; i<n; i++) if(!vis[i]) { dfs(i); reroot(i); int res=2e9; for(int v : vec) res = min(res, dp[v]); diams.push_back(res); vec.clear(); } sort(diams.begin(), diams.end()); int ans = *max_element(dp, dp+n); if(SZ(diams)>=2) ans = max(ans, diams[SZ(diams)-1]+diams[SZ(diams)-2]+l); if(SZ(diams)>=3) ans = max(ans, diams[SZ(diams)-2]+diams[SZ(diams)-3]+l+l); return ans; }
#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...