| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 638620 | ojoConmigo | 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>
using namespace std;
vector<vector<pair<int,int>>> g;
vector<bool> visit;
vector<int> fir,sec,ans;
int x;
void dfs1(int nodo, int p){
visit[nodo] = true;
for(auto k : g[nodo]){
int v = k.first;
int w = k.second;
if(v == p)continue;
dfs1(v,nodo);
if(fir[v] + w > fir[nodo]){
sec[nodo] = fir[nodo];
fir[nodo] = fir[v] + w;
}else if(fir[v] + w > sec[nodo]){
sec[nodo] = fir[v] + w;
}
}
}
int dfs2(int nodo, int p, int top){
ans[nodo] = max(fir[nodo],top);
int cont = ans[nodo];
for(auto k : g[nodo]){
int v = k.first;
int w = k.second;
if(v == p)continue;
if(fir[v] + w == fir[nodo]) cont = min(cont,dfs2(v,nodo,max(top,sec[nodo]) + w));
else cont = min(cont,dfs2(v,nodo,ans[nodo] + w));
}
return cont;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
g.resize(N);
for(int i=0; i<M; i++){
int x = A[i];
int y = B[i];
int w = T[i];
g[x].push_back({y,w});
g[y].push_back({x,w});
}
visit.assign(N,false);
fir.assign(N,0);
sec.assign(N,0);
ans.resize(N);
int m1,m2,m3;
m1 = m2 = m3 = 0;
for(int i=0; i<N; i++){
if(!visit[i]){
dfs1(i,-1);
int q = dfs2(i,-1,0);
if(q > m1){
m3 = m2;
m2 = m1;
m1 = q;
}else if(q > m2){
m3 = m2;
m2 = q;
}else if(q > m3){
m3 = q;
}
//cout << i << " " << q << endl;
}
}
return max(m1+m2+L,m2+m3+2*L);
}
/*
int main(){
int n,m,l;
cin >> n >> m >> l;
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) << endl;
}
*/