Submission #1015500

#TimeUsernameProblemLanguageResultExecution timeMemory
1015500lalig777Dreaming (IOI13_dreaming)C++14
100 / 100
46 ms15592 KiB
#include "dreaming.h" #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int ll; vector<vector<pair<int, int>>> g; vector<bool>used; vector<int>ans; vector<pair<int, int>>dp; int res=2e9; int maxdiam=0; void dfs1(int u){ used[u]=true; for(pair<int, int> vec:g[u]){ int v=vec.first, c=vec.second; if (used[v]) continue; dfs1(v); if (dp[u].first<dp[v].first+c){ dp[u].second=dp[u].first; dp[u].first=dp[v].first+c; }else if (dp[u].second<dp[v].first+c){ dp[u].second=dp[v].first+c; } }return; } void dfs2(int u, int p, int maxi){ int maxim=maxi; res=min(res, max(maxim,dp[u].first)); maxdiam=max(maxdiam, max(maxim, dp[u].first)); for(pair<int, int> vec:g[u]){ int v=vec.first, c=vec.second; if (v==p) continue; if (dp[u].first==dp[v].first+c) maxi=max(maxim+c, dp[u].second+c); else maxi=max(maxim, dp[u].first+c); dfs2(v, u, maxi); }return; } int travelTime(int N, int M, int L, int A[], int B[], int T[]){ g.resize(N); used.assign(N, false); dp.assign(N, {0, 0}); 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]}); }for (int i=0; i<N; i++){ if (used[i]) continue; res=2e9; dfs1(i); dfs2(i, -1, 0); ans.push_back(res); }sort(ans.begin(), ans.end()); reverse(ans.begin(), ans.end()); if (ans.size()==1) return max(maxdiam, ans[0]); if (ans.size()==2) return max(maxdiam, ans[0]+ans[1]+L); return max(maxdiam, max(ans[0]+ans[1]+L, ans[1]+ans[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...