Submission #1198633

#TimeUsernameProblemLanguageResultExecution timeMemory
1198633bestbestDreaming (IOI13_dreaming)C++20
100 / 100
123 ms13004 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define en '\n' #define sp ' ' typedef long long ll; #define pii pair<int,int> const int N=1e5+10; vector<pii> adj[N]; vector<int> st,ans; int target,start; vector<int> par(N); vector<int> vis(N); int mx,mxn,node; int mxdia; void dfs1(int u,int p,int nw){ vis[u]=1; // cout << u << sp; if(mxn<nw){ mxn=nw; node=u; } for(auto [v,w]:adj[u]){ if(v==p)continue; dfs1(v,u,nw+w); } return ; } void dfs2(int u,int p,int nw){ par[u]=p; // cout << 's' << u << sp <<p << en; if(mx<nw){ mx=nw; target=u; } for(auto [v,w]:adj[u]){ if(v==p)continue; dfs2(v,u,nw+w); } return; } 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]){ mx=0,mxn=0,node=i,target=i; dfs1(i,-1,0); start=node; dfs2(start,-1,0); int trav=target; st.push_back(0); while (par[trav]!=-1) { int weight=0; for(auto [v,w]:adj[trav]){ if(v==par[trav]){ weight=w+st.back(); break; } } st.push_back(weight); trav=par[trav]; } int mi=1e9; for(int i=0;i<st.size();i++){ mi=min(mi,max(st[i],st.back()-st[i])); } mxdia=max(mxdia,st.back()); ans.push_back(mi); st.clear(); } } sort(ans.begin(),ans.end(),greater<int>()); if(ans.size()==1){ return mxdia; } else if(ans.size()==2){ return max(mxdia,ans[0]+ans[1]+l); } return max(mxdia,max(ans[0]+ans[1]+l,ans[1]+ans[2]+l*2 ) ); }
#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...