Submission #970664

#TimeUsernameProblemLanguageResultExecution timeMemory
970664yeediotDreaming (IOI13_dreaming)C++17
100 / 100
56 ms16188 KiB
#include<bits/stdc++.h> #include "dreaming.h" using namespace std; #define F first #define S second #define chmin(a,b) a=(a<b?a:b) #define chmax(a,b) a=(a>b?a:b) const int mxn=1e5+5; vector<pair<int,int>>adj[mxn]; pair<int,int>dp[mxn]; bool vis[mxn]; int dp2[mxn]; void dfs(int v,int pa){ vis[v]=1; for(auto [u,len]:adj[v]){ if(u==pa) continue; dfs(u,v); if(dp[v].F<=dp[u].F+len){ dp[v].S=dp[v].F; dp[v].F=dp[u].F+len; } else if(dp[v].S<dp[u].F+len){ dp[v].S=dp[u].F+len; } } } pair<int,int> mn; int mx=0; void reroot(int v,int pa){ chmin(mn,make_pair(dp[v].F,v)); for(auto [u,len]:adj[v]){ if(u==pa) continue; int x; if(dp[v].F!=dp[u].F+len){ x=dp[v].F; } else{ x=dp[v].S; } x+=len; if(dp[u].F<=x){ dp[u].S=dp[u].F; dp[u].F=x; } else if(dp[u].S<x){ dp[u].S=x; } reroot(u,v); } } void dfs2(int v,int pa){ for(auto [u,len]:adj[v]){ if(u==pa) continue; dfs2(u,v); chmax(mx,dp2[v]+dp2[u]+len); chmax(dp2[v],dp2[u]+len); } } vector<pair<int,int>>v; int travelTime(int n,int m,int l,int a[],int b[],int t[]){ for(int i=0;i<m;i++){ adj[a[i]].push_back({b[i],t[i]}); adj[b[i]].push_back({a[i],t[i]}); } for(int i=0;i<n;i++){ if(vis[i]) continue; mn={2e9,2e9}; dfs(i,i); reroot(i,i); v.push_back(mn); } sort(v.begin(),v.end(),greater<pair<int,int>>()); for(int i=1;i<(int)v.size();i++){ adj[v[0].S].push_back({v[i].S,l}); adj[v[i].S].push_back({v[0].S,l}); } dfs2(0,0); return mx; } #ifdef local int main(){ freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin); int n,m,l; cin>>n>>m>>l; int a[m],b[m],t[m]; for(int i=0;i<m;i++){ cin>>a[i]>>b[i]>>t[i]; } cout<<travelTime(n,m,l,a,b,t)<<'\n'; } #else #endif
#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...