# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
897394 | Sir_Ahmed_Imran | 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.
///~~~LOTA~~~///
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 100000
int ans;
int vis[N];
int dp1[N];
int dp2[N];
int dp3[N];
vector<pii> a[N];
void dfs(int v){
vis[v]=1;
for(auto& i:a[v]){
if(vis[i.ff]) continue;
dfs(i.ff);
if(dp1[i.ff]+i.ss>dp1[v]){
dp2[v]=dp1[v];
dp1[v]=dp1[i.ff]+i.ss;
}
else
dp2[v]=max(dp2[v],dp1[i.ff]+i.ss);
}
}
int dfs2(int v,int u){
ans=max(ans,dp1[v]+dp2[v]);
ans=max(ans,dp1[v]+dp3[v]);
int o=max(dp1[v],dp3[v]);
for(auto& i:a[v]){
if(i.ff==u)
continue;
dp3[i.ff]=dp3[v]+i.ss;
if(dp1[i.ff]+i.ss==dp1[v])
dp3[i.ff]=max(dp3[i.ff],dp2[v]+i.ss);
else dp3[i.ff]=max(dp3[i.ff],dp1[v]+i.ss);
o=min(o,dfs2(i.ff,v));
}
return o;
}