Submission #1198634

#TimeUsernameProblemLanguageResultExecution timeMemory
1198634bestbestDreaming (IOI13_dreaming)C++20
100 / 100
99 ms13516 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]; multiset<int,greater<int>>s; vector<int> st; int target,start; vector<int> qs(N),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]}); } // cout << en; for(int i=0;i<n;i++){ if(!vis[i]){ // cout << "i" << i << sp; mx=0,mxn=0,node=i,target=i; dfs1(i,-1,0); // cout << en; // cout << i << sp << mxn << sp << node << en; start=node; dfs2(start,-1,0); int trav=target; // for(int i=0;i<n;i++)cout << par[i] << sp; // cout << en; st.push_back(0); while (par[trav]!=-1) { // cout << trav << sp; int weight=0; for(auto [v,w]:adj[trav]){ if(v==par[trav]){ weight=w; break; } } st.push_back(weight); trav=par[trav]; } // cout << trav; // cout << en; for(int i=1;i<st.size();i++){ st[i]+=st[i-1]; // cout << st[i] << sp; } // cout << en; // cout << target << sp << qs[st.size()-1] << en; 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()); // cout << "mi " << mi << en; // if(mi==1e9)s.insert(0); // else s.insert(mi); s.insert(mi); st.clear(); // cout << en; } } // for(int i:s)cout << i << sp; // int f1=q.top(); // q.pop(); // int f2=q.top(); int f1,f2; if(s.size()==1){ return mxdia; } else if(s.size()==2){ f1=*s.begin(),f2=*next(s.begin()); return max(mxdia,f1+f2+l); } f1=*s.begin(),f2=*next(s.begin()); int f3=*next(next(s.begin())); return max(mxdia,max(f1+f2+l,f2+f3+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...