#include "grader.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
vector< pair<int,int> > adj[100005];
int vis[100005],mem[100005],mem2[100005];
int hi[100005],id[100005],maxi[100005];
int n;
void dfs(int node,int pa,int h)
{
vis[node]=1;
hi[node]=h;
for(int i=0;i<adj[node].size();i++)
{
if(adj[node][i].F==pa)
continue;
dfs(adj[node][i].F,node,h+adj[node][i].S);
mem[node]=max(mem[node],mem[adj[node][i].F]+adj[node][i].S);
}
}
void dfs2(int node,int pa,int maxi,int idc)
{
//cout << node << " " << pa << " " << maxi << endl;
vis[node]=0; id[node]=idc;
vector<int> ch;
for(int i=0;i<adj[node].size();i++)
{
if(adj[node][i].F==pa)
continue;
ch.push_back(mem[adj[node][i].F]+adj[node][i].S);
}
//cout << "OK " << ch.size() << endl;
sort(ch.begin(),ch.end()); reverse(ch.begin(),ch.end());
mem2[node]=max(max(maxi,hi[node]),ch.size()?ch[0]:0);
for(int i=0;i<adj[node].size();i++)
{
if(adj[node][i].F==pa)
continue;
int oth=(ch[0]==mem[adj[node][i].F]+adj[node][i].S?(ch.size()>1?ch[1]:0):ch[0]);
dfs2(adj[node][i].F,node,max(maxi,oth)+adj[node][i].S,idc);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
for(int i=0;i<M;i++)
{
adj[A[i]].push_back({B[i],T[i]});
adj[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<N;i++)
{
if(!vis[i])
dfs(i,-1,0);
}
int idc=1;
for(int i=0;i<N;i++)
{
if(vis[i])
dfs2(i,-1,0,idc++);
}
for(int i=0;i<N;i++)
maxi[i]=(1<<30);
for(int i=0;i<N;i++)
maxi[id[i]]=min(maxi[id[i]],mem2[i]);
vector<int> v;
for(int i=1;i<idc;i++)
v.push_back(maxi[i]);
sort(v.begin(),v.end()); reverse(v.begin(),v.end());
int maxr=0;
for(int i=0;i<N;i++)
maxr=max(maxr,mem2[i]);
if(v.size()==1)
return maxr;
else if(v.size()==2)
return max(maxr,v[0]+L+v[1]);
return max(maxr,max(v[0]+L+v[1],2*L+v[1]+v[2]));
}
Compilation message
dreaming.cpp:1:10: fatal error: grader.h: No such file or directory
1 | #include "grader.h"
| ^~~~~~~~~~
compilation terminated.
