#include "dreaming.h"
#include <bits/stdc++.h>
#define MAX 200001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
for(int i=0;i<b;i++){\
cin >> a[i];\
}\
}
#define inputvec(a,b){\
for(int i=0;i<b;i++){\
ll num;\
cin >> num;\
a.pb(num);\
}\
}
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << x << " ";\
}\
cout << "\n";\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int h;
vector<bool> used;
vector<int> dist;
vector<int> maxdist1;
vector<pair<pii,pii>> maxdist;
vector<vector<pii>> g;
vector<int> b;
void dfs(int v,int prev){
used[v]=true;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dist[x.ff]=dist[v]+x.ss;
dfs(x.ff,v);
}
}
void dfs1(int v,int prev){
used[v]=true;
maxdist1[v]=dist[v];
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dfs1(x.ff,v);
maxdist1[v]=max(maxdist1[v],maxdist1[x.ff]);
}
}
void dfs2(int v,int prev){
used[v]=true;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
if(maxdist1[x.ff]>maxdist[v].ff.ff){
maxdist[v].ss=max(maxdist[v].ss,maxdist[v].ff);
maxdist[v].ff=mp(maxdist1[x.ff],x.ff);
}
else if(maxdist1[x.ff]>maxdist[v].ss.ff){
maxdist[v].ss=mp(maxdist1[x.ff],x.ff);
}
dfs2(x.ff,v);
}
}
void dfs3(int v,int prev){
int h1=0;
h1=max(h1,maxdist1[v]-dist[v]);
if(prev!=-1){
pair<pii,pii> p1=maxdist[prev];
pii p2,p3;
p2=p1.ff;
p3=p1.ss;
b[v]=b[prev]+dist[v]-dist[prev];
if(p2.ss!=v && p2.ff!=-INF){
b[v]=max(b[v],p2.ff+dist[v]-dist[prev]);
}
else if(p3.ff!=-INF){
b[v]=max(b[v],p3.ff+dist[v]-dist[prev]);
}
h1=max(h1,b[v]);
}
h=min(h,h1);
used[v]=true;
for(auto x:g[v]){
if(x.ff==prev){
continue;
}
dfs3(x.ff,v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int res;
g.resize(N);
dist.resize(N,0);
used.resize(N,0);
b.resize(N,0);
pair<pii,pii> a;
a=mp(mp(-INF,-INF),mp(-INF,-INF));
maxdist.resize(N,a);
maxdist1.resize(N);
for(int i=0;i<M;i++){
g[A[i]].pb(mp(B[i],T[i]));
g[B[i]].pb(mp(A[i],T[i]));
}
for(int i=0;i<N;i++){
if(!used[i]){
dfs(i,-1);
}
}
for(int i=0;i<N;i++){
used[i]=false;
}
for(int i=0;i<N;i++){
if(!used[i]){
dfs1(i,-1);
}
}
for(int i=0;i<N;i++){
used[i]=false;
}
for(int i=0;i<N;i++){
if(!used[i]){
dfs2(i,-1);
}
}
for(int i=0;i<N;i++){
used[i]=false;
}
vector<int> c;
for(int i=0;i<N;i++){
if(!used[i]){
h=INF;
dfs3(i,-1);
c.pb(h);
}
}
sortv(c);
reverse(all(c));
if(c.size()==1){
res=c[0];
}
else{
res=c[0]+c[1]+L;
}
/*
for(int i=0;i<N;i++){
cout << i << " " << dist[i] << " " << maxdist[i].ff.ff << " " << maxdist[i].ff.ss << " " << maxdist[i].ss.ff << " " << maxdist[i].ss.ss << "\n";
}
*/
return res;
}
/*
int main(){
int n,m,k;
cin >> n >> m >> k;
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,k,A,B,T);
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
8360 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
8288 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
