#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include "grader.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class WTree
{
public:
ll N;
vector<ll> p;
vector<vector<pl> > sons;
vector<vector<pl> > adj;
ll root;
vector<bool> visited;
vector<vector<ll> > farthest_dir;
vector<ll> farthest_down;
vector<ll> farthest_up;
vector<ll> farthest;
vector<ll> dist;
pair<ll,pl> diametre;
WTree(vector<vector<pl> > ad, ll r=0LL)
{
N=ad.size(); root=r; adj=ad;
vector<pl> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);}
REP(i,0,N) {visited.pb(false);}
DFS_Build(r,r);
vector<ll> xxx;
REP(i,0,N) {farthest_up.pb(0); farthest_down.pb(0); farthest_dir.pb(xxx); farthest.pb(0);}
REP(i,0,N) {REP(j,0,adj[i].size()) {farthest_dir[i].pb(0);}}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS_Build(ll s, ll par)
{
p[s]=par;
visited[s]=true;
REP(i,0,adj[s].size())
{
if(adj[s][i].ff==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i].ff,s);
}
return;
}
void DFS_distance(ll s, ll las)
{
REP(i,0,adj[s].size())
{
if(adj[s][i].ff==las) {continue;}
dist[adj[s][i].ff]=dist[s]+adj[s][i].ss;
DFS_distance(adj[s][i].ff,s);
}
}
void distance(ll s)
{
dist.clear(); REP(i,0,N) {dist.pb(INF);}
dist[s]=0LL;
DFS_distance(s,s);
}
void Calc_Diametre()
{
distance(root);
vector<ll>::iterator it=max_element(whole(dist));
ll ind=it-dist.begin();
distance(ind);
diametre.ss.ff=ind;
it=max_element(whole(dist));
diametre.ss.ss=it-dist.begin();
diametre.ff=*it;
}
void Calc_farthest_down(ll s)
{
REP(i,0,sons[s].size()) {Calc_farthest_down(sons[s][i].ff);}
REP(i,0,adj[s].size())
{
if(adj[s][i].ff==p[s]) {continue;}
farthest_dir[s][i]=farthest_down[adj[s][i].ff]+adj[s][i].ss;
farthest_down[s]=max(farthest_down[s],farthest_dir[s][i]);
}
}
void Calc_farthest_up(ll s)
{
if(s==root) {farthest_up[s]=0LL;}
pl best_dis=mp(0,0);
REP(i,0,adj[s].size())
{
if(farthest_dir[s][i]>best_dis.ff) {best_dis.ss=best_dis.ff; best_dis.ff=farthest_dir[s][i];}
else if(farthest_dir[s][i]>best_dis.ss) {best_dis.ss=farthest_dir[s][i];}
}
REP(i,0,adj[s].size())
{
if(adj[s][i].ff==p[s]) {continue;}
ll c = adj[s][i].ff;
if(best_dis.ff == farthest_dir[s][i]) {farthest_up[c] = best_dis.ss+adj[s][i].ss;}
else {farthest_up[c]=best_dis.ff+adj[s][i].ss;}
REP(j,0,adj[c].size()) {if(adj[c][j].ff==s) {farthest_dir[c][j]=farthest_up[c];}}
}
REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i].ff);}
}
void Calc_farthest()
{
Calc_farthest_down(root);
Calc_farthest_up(root);
REP(i,0,N) {farthest[i]=max(farthest_up[i],farthest_down[i]);}
}
pl Radius() //returns {centre, radius}
{
Calc_farthest();
ll ind=0LL; ll val = farthest[0];
REP(i,1,N)
{
if(farthest[i]<val) {val=farthest[i]; ind=i;}
}
return (pl) {ind,val};
}
};
class WG //everything works for weighted directed graphs except dynamic graph
{
public:
ll N; vector<vector<pl> > adj;
vector<bool> visited;
vector<ll> current;
WG(vector<vector<pl> > ad)
{
adj=ad; N=adj.size();
REP(i,0,N) {visited.pb(false);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS(ll s)
{
if(visited[s]) {return;}
visited[s]=true;
current.pb(s); //only needed for CC
REP(i,0,adj[s].size())
{
if(!visited[adj[s][i].ff]) {DFS(adj[s][i].ff);}
}
return;
}
vector<vector<ll> > CC()
{
Reset();
ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
vector<vector<ll> > ans;
while(missing>0)
{
REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
current.clear();
DFS(fi);
ans.pb(current);
missing-=current.size();
}
return ans;
}
vector<WTree> CCG()
{
Reset();
vector<WTree> ans;
vector<vector<ll> > CC=(*this).CC();
unordered_map<ll,ll> m; vector<pl> xx; vector<vector<pl> > ad;
REP(cc,0,CC.size())
{
m.clear();
ad.clear();
ll NN=CC[cc].size();
REP(i,0,NN) {ad.pb(xx);}
REP(i,0,NN) {m[CC[cc][i]]=i;}
ll a,b;
REP(i,0,NN)
{
a=CC[cc][i];
REP(j,0,adj[a].size()) {b=adj[a][j].ff; ad[i].pb({m[b],adj[a][j].ss});}
}
WTree H(ad);
ans.pb(H);
}
return ans;
}
};
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
int a;
ll N = (ll) n; ll M = (ll) m; vector<pl> xx; vector<vector<pl> > adj; REP(i,0,N) {adj.pb(xx);}
REP(i,0,M)
{
adj[A[i]].pb({B[i],T[i]}); adj[B[i]].pb({A[i],T[i]});
}
WG G(adj);
vector<WTree> F = G.CCG();
ll ans = 0LL;
REP(i,0,F.size()) {F[i].Calc_Diametre(); ans=max(ans,F[i].diametre.ff);}
vector<ll> R; REP(i,0,F.size()) {R.pb(F[i].Radius().ss);}
sort(whole(R)); reverse(whole(R));
if(R.size()>=2) {ans=max(ans,L+R[0]+R[1]);}
if(R.size()>=3) {ans=max((ll) ans,(ll) 2LL*L+R[1]+R[2]);}
return ans;
}
Compilation message
dreaming.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization ("O3")
|
dreaming.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("unroll-loops")
|
dreaming.cpp:4:10: fatal error: grader.h: No such file or directory
4 | #include "grader.h"
| ^~~~~~~~~~
compilation terminated.
