Submission #923973

#TimeUsernameProblemLanguageResultExecution timeMemory
923973ArpDreaming (IOI13_dreaming)C++17
100 / 100
55 ms17344 KiB
#include<bits/stdc++.h> #include "dreaming.h" using namespace std; const int N = 1e5; const int inf = 2e9; vector<pair<int,int>> adj[N]; int down[N],up[N]; bool vis[N]; void dfs(int u){ vis[u] = true; vector<pair<int,int>> all; for(auto [v,w] : adj[u]){ if(vis[v]) continue; dfs(v); all.emplace_back(v,w); } int maxi = -inf; for(auto [v,w] : all){ up[v] = max(up[v],maxi + w); maxi = max(maxi,down[v] + w); } reverse(all.begin(),all.end()); maxi = -inf; for(auto [v,w] : all){ up[v] = max(up[v],maxi + w); maxi = max(maxi,down[v] + w); down[u] = maxi; } } int mini = inf; void dfs2(int u,int p){ for(auto[v,w] : adj[u]){ if(v == p) continue; up[v] = max(up[v],up[u] + w); dfs2(v,u); } mini = min(mini,max(down[u],up[u])); } int travelTime(int N,int M,int L,int A[],int B[],int T[]){ for(int i = 0;i<N;i++){ up[i] = down[i] = 0; vis[i] = false; } for(int i = 0;i<M;i++){ adj[A[i]].emplace_back(B[i],T[i]); adj[B[i]].emplace_back(A[i],T[i]); } vector<int> arr; int ans = 0; int cc = 0; for(int i = 0;i<N;i++){ if(!vis[i]){ mini = inf; dfs(i); dfs2(i,-1); arr.push_back(mini); cc ++; } ans = max(ans,up[i]); } assert(cc - 1 == N - M - 1); sort(arr.begin(),arr.end()); int tot = inf; if(arr.size() == 1){ return ans; } if(arr.size() == 2){ return max(ans,arr[0] + arr[1] + L); }else if(arr.size() > 2){ int a = arr[arr.size() - 3]; int b = arr[arr.size() - 2]; int c = arr[arr.size() - 1]; tot = min(tot,max(b + c + L,a + c + 2 * L)); tot = min(tot,max(b + c + L,a + b + 2 * L)); } return max(tot,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...