| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 388397 | cpp219 | Dreaming (IOI13_dreaming) | C++14 | 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.
#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e5 + 6;
const ll lim = 3e5 + 6;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<ll> v;
vector<LL> g[N];
bool dd[N];
ll now = 1,L[N],R[N],d[N],pos[N],lens,par[N];
void DFS(ll u,ll p){
dd[u] = 1; L[u] = R[u] = now; pos[now] = u; now++;
for (auto i : g[u]){
ll v = i.fs,L = i.sc;
if (v != p) d[v] = d[u] + L,DFS(v,u),par[v] = u,R[u] = max(R[u],R[v]);
}
}
ll farthest(ll root){
now = 1; d[root] = 0; par[root] = -1; DFS(root,0); ll mx = -5,chosen;
for (ll i = L[root];i <= R[root];i++){
ll now = pos[i];
if (mx < d[now]) chosen = now,mx = d[now];
//cout<<now<<" "<<d[now]<<"\n";
}
return chosen;
}
ll Find_opt(ll now,ll total){
ll mn = inf;
while(now >= 0){
ll low = total - d[now],high = d[now];
//cout<<low<<" "<<high<<"\n";
if (max(low,high) < mn) mn = min(mn,max(low,high));
now = par[now];
}
//exit(0);
return mn;
}
bool lf(ll x,ll y){
return x > y;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
ll ans = 0;
for (ll i = 0;i < m;i++){
g[A[i]].push_back({B[i],T[i]}); g[B[i]].push_back({A[i],T[i]});
}
for (ll i = 0;i < n;i++){
if (!dd[i]){
ll p = farthest(i); ll nxt = farthest(p);
ans = max(ans,d[nxt]); v.push_back(Find_opt(nxt,d[nxt]));
}
}
sort(v.begin(),v.end(),lf);
//for (auto i : v) cout<<i<<" ";
//exit(0);
if (v.size() >= 2) ans = max(ans,v[0] + v[1] + L);
if (v.size() > 2) ans = max(ans,v[1] + v[2] + 2*L);
return ans;
}
/*
ll n,m,Len,A[N],B[N],T[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>m>>Len;
for (ll i = 0;i < m;i++) cin>>A[i]>>B[i]>>T[i];
cout<<travelTime(n,m,Len,A,B,T);
}
*/