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 int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n;
bool visited[MAXN];
int parents[MAXN];
vector<vector<pii>> graf(MAXN);
vector<long long> dist;
long long mxdist;
long long rez = inf;
long long konacno= 0;
void dfs1(int nod, int p, long long d, int &kraj)
{
parents[nod] = p;
visited[nod] = 1;
if(d>=mxdist)
{
kraj = nod;
mxdist = d;
}
for(auto x: graf[nod])if(x.fi!=p)dfs1(x.fi, nod, d+x.sc, kraj);
}
void dfs2(int nod, int p, long long d)
{
rez = min(rez, max(mxdist -d, d));
int tr = rez;
for(auto x: graf[nod])
{
if(x.fi == p)continue;
int p1 = parents[nod];
if(parents[nod] == x.fi)
{
dfs2(x.fi, nod, d+x.sc);
}
}
}
void solve(int i)
{
int nod1 = i;
mxdist = 0;
dfs1(i,i,0, nod1);
int nod2 = i;
mxdist = 0;
dfs1(nod1, nod1, 0, nod2);
rez = inf;
dfs2(nod2, nod2, 0);
konacno = max(konacno, mxdist);
dist.pb(rez);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
for(int i=0; i<M; i++)
{
graf[A[i]].pb(mp(B[i], T[i]));
graf[B[i]].pb(mp(A[i], T[i]));
}
for(int i=0; i<n; i++)if(!visited[i])solve(i);
sort(all(dist));
reverse(all(dist));
//for(auto x: dist)cout << x<< " ";cout << endl;
if(dist.size() == 1)return konacno;
konacno = max(konacno,dist[0]+dist[1]+L);
if(dist.size()>2) konacno = max(konacno,dist[1]+dist[2]+2*L);
return konacno;
}
Compilation message (stderr)
dreaming.cpp: In function 'void dfs2(int, int, long long int)':
dreaming.cpp:45:13: warning: unused variable 'p1' [-Wunused-variable]
45 | int p1 = parents[nod];
| ^~
dreaming.cpp:41:9: warning: unused variable 'tr' [-Wunused-variable]
41 | int tr = rez;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |