| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 396553 | Jasiekstrz | 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 "dreaming.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
vector<pair<int,int>> e[NN+10];
bool vis[NN+10];
int dp[NN+10];
int mx[NN+10][2];
void dfs(int x)
{
vis[x]=true;
int mx1=0,mx2=0;
for(auto v:e[x])
{
if(!vis[v.fi])
{
dfs(v.fi);
dp[x]=max(dp[x],dp[v.fi]+v.se);
if(dp[v.fi]+v.se>=mx1)
{
mx2=mx1;
mx1=dp[v.fi]+v.se;
}
else if(dp[v.fi]+v.se>=mx2)
mx2=dp[v.fi]+v.se;
}
}
mx[x][0]=mx1;
mx[x][1]=mx2;
return;
}
void swp(int x,int y,int c)
{
if(mx[x][0]==dp[y])
dp[x]=mx[x][1];
else
dp[x]=mx[x][0];
if(dp[x]+c>=mx[y][0])
{
mx[y][1]=mx[y][0];
mx[y][0]=dp[x]+c;
}
else if(dp[x]+c>mx[y][1])
mx[y][1]=dp[x]+c;
dp[y]=mx[y][0];
return;
}
int dfs2(int x,int p)
{
int ans=dp[x];
for(auto v:e[x])
{
if(v.fi==p)
continue;
swp(x,v.fi,v.se);
ans=min(ans,dfs2(v.fi,x));
swp(v.fi,x,v.se);
}
return ans;
}
int travelTime(int N,int M,int L,vector<int> A,vector<int> B,vector<int> T)
{
for(int i=0;i<M;i++)
{
e[A[i]].emplace_back(B[i],T[i]);
e[B[i]].emplace_back(A[i],T[i]);
}
vector<int> tab={0,0,0};
for(int i=1;i<=N;i++)
{
if(!vis[i])
{
dfs(i);
tab.push_back(dfs2(i,0));
}
}
sort(tab.begin(),tab.end());
reverse(tab.begin(),tab.end());
return max(tab[0]+tab[1]+L,tab[1]+tab[2]+2*L);
}
//int main()
//{
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// int n,m,l;
// cin>>n>>m>>l;
// vector<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";
// return 0;
//}