| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 860884 | tosivanmak | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll,ll> >adj[100005];
bool visited[100005],visited2[100005],visited3[100005];
ll dist[100005],maxdep[100005];
set<pair<ll,ll> >st[100005],st2[100005];
void dfs(ll s){
visited[s]=true;
maxdep[s]=dist[s];
for(auto u: adj[s]){
if(!visited[u.first]){
dist[u.first]=dist[s]+u.second;
dfs(u.first);
maxdep[s]=max(maxdep[s],maxdep[u.first]);
}
}
}
ll find(ll s, ll longest){
visited2[s]=true;
ll haha=max(maxdep[s]-dist[s],longest);
for(auto u: adj[s]){
if(!visited2[u.first]){
st[s].insert({maxdep[u.first],u.first});
}
}
for(auto u: adj[s]){
if(!visited2[u.first]){
st[s].erase({maxdep[u.first],u.first});
ll lol=u.second+longest;
if(st[s].size()){
pair<ll,ll> bruh=*st[s].rbegin();
ll ok=bruh.first;
ok+=u.second;
ok-=dist[s];
lol=max(lol,ok);
}
haha=min(haha,find(u.first,lol));
st[s].insert({maxdep[u.first],u.first});
}
}
return haha;
}
ll find2(ll s, ll longest){
// cout<<s<<": "<<longest<<"\n";
visited3[s]=true;
ll haha=max(maxdep[s]-dist[s],longest);
for(auto u: adj[s]){
if(!visited3[u.first]){
st2[s].insert({maxdep[u.first],u.first});
}
}
for(auto u: adj[s]){
if(!visited3[u.first]){
st2[s].erase({maxdep[u.first],u.first});
ll lol=u.second+longest;
if(st2[s].size()){
pair<ll,ll> bruh=*st2[s].rbegin();
ll ok=bruh.first;
ok+=u.second;
ok-=dist[s];
lol=max(lol,ok);
}
haha=max(haha,find2(u.first,lol));
st2[s].insert({maxdep[u.first],u.first});
}
}
return haha;
}
// int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL); cout.tie(NULL);
// ll n,m,l;
// cin>>n>>m>>l;
// // largest + second +l
// // or second + third + 2*l
// // maximum
// for(int i=1;i<=m;i++){
// ll u,v,t;
// cin>>u>>v>>t;
// adj[u].push_back({v,t});
// adj[v].push_back({u,t});
// }
// vector<ll>ans,ans2;
// for(int i=0;i<n;i++){
// if(!visited[i]){
// dist[i]=0;
// dfs(i);
// // cout<<i<<": ";
// ans.push_back(find(i,0));
// ans2.push_back(find2(i,0));
// }
// }
// // for(int i=0;i<n;i++){
// // cout<<dist[i]<<" ";
// // }
// sort(ans.rbegin(),ans.rend());
// sort(ans2.rbegin(),ans2.rend());
// if(m==n-1){
// cout<<ans2[0]<<"\n";
// }
// else if(m==n-2){
// cout<<max(ans2[0],ans[0]+ans[1]+l);
// }
// else{
// ll lol=ans[0]+ans[1]+l;
// lol=max(lol,ans[1]+ans[2]+2*l);
// lol=max(lol,ans2[0]);
// cout<<lol<<'\n';
// }
// // for(auto u: ans2){
// // cout<<u<<"\n";
// // }
// // for(auto u: ans){
// // cout<<u<<" ";
// // }
// }
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
int n,m,l;
n=N,m=M,l=L;
// largest + second +l
// or second + third + 2*l
// maximum
for(int i=0;i<m;i++){
ll u,v,t;
u=A[i],v=B[i],t=T[i];
adj[u].push_back({v,t});
adj[v].push_back({u,t});
}
vector<int>ans,ans2;
for(int i=0;i<n;i++){
if(!visited[i]){
dist[i]=0;
dfs(i);
// cout<<i<<": ";
ans.push_back(find(i,0));
ans2.push_back(find2(i,0));
}
}
// for(int i=0;i<n;i++){
// cout<<dist[i]<<" ";
// }
sort(ans.rbegin(),ans.rend());
sort(ans2.rbegin(),ans2.rend());
if(m==n-1){
// cout<<ans2[0]<<"\n";
return ans2[0];
}
else if(m==n-2){
return max(ans2[0],ans[0]+ans[1]+l);
}
else{
ll lol=ans[0]+ans[1]+l;
lol=max(lol,ans[1]+ans[2]+2*l);
lol=max(lol,ans2[0]);
return lol;
}
}