| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 284423 | PedroBigMan | Dreaming (IOI13_dreaming) | C++14 | 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 <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 long long 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 50000000000LL
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);}}
struct hash_pair
{
template <class T1, class T2>
size_t operator() (pair<T1, T2> p) const
{
size_t hash1 = hash<T1>()(p.first);
size_t hash2 = hash<T2>()(p.second);
return (hash1 ^ hash2);
}
};
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<ll> visited; //for DFS/BFS
vector<ll> current; //for CC
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
current.clear();
}
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]]) {DFS(adj[s][i]);}
}
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;
}
};
class Tree
{
public:
ll N;
vector<ll> p;
vector<vector<ll> > sons;
vector<vector<ll> > adj;
ll root;
vector<bool> visited;
vector<ll> level; //starting in 0
vector<ll> sub; //number of nodes in subtree
vector<ll> val; //node values
vector<ll> dist;
pair<ll,pl> diametre;
vector<vector<ll> > farthest_dir;
vector<ll> farthest_down;
vector<ll> farthest_up;
vector<ll> farthest;
Tree(vector<vector<ll> > ad, ll r=0LL)
{
N=ad.size(); root=r; adj=ad;
REP(i,0,N) {visited.pb(false);}
vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0); sub.pb(1LL);}
DFS_Build(r,r);
REP(i,0,N) {val.pb(0LL);}
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)
{
if(s!=root) {level[s]=level[par]+1LL;}
p[s]=par;
visited[s]=true;
REP(i,0,adj[s].size())
{
if(adj[s][i]==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i],s);
sub[s]+=sub[adj[s][i]];
}
return;
}
void DFS_distance(ll s, ll las)
{
REP(i,0,adj[s].size())
{
if(adj[s][i]==las) {continue;}
if(adj[s][i]==p[s]) {dist[adj[s][i]]=dist[s]+val[s];}
else {dist[adj[s][i]]=dist[s]+val[adj[s][i]];}
DFS_distance(adj[s][i],s);
}
}
void distance(ll s)
{
dist.clear(); REP(i,0,N) {dist.pb(INF);}
dist[s]=0;
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]);}
REP(i,0,adj[s].size())
{
if(adj[s][i]==p[s]) {continue;}
farthest_dir[s][i]=farthest_down[adj[s][i]]+val[adj[s][i]];
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]==p[s]) {continue;}
ll c = adj[s][i];
if(best_dis.ff == farthest_dir[s][i]) {farthest_up[c] = best_dis.ss+val[c];}
else {farthest_up[c]=best_dis.ff+val[c];}
REP(j,0,adj[c].size()) {if(adj[c][j]==s) {farthest_dir[c][j]=farthest_up[c];}}
}
REP(i,0,sons[s].size()) {Calc_farthest_up(sons[s][i]);}
}
void Calc_farthest()
{
REP(i,0,N) {farthest[i]=max(farthest_up[i],farthest_down[i]);}
}
};
class WTree
{
public:
ll N;
vector<ll> p;
vector<vector<pl> > sons;
vector<vector<pl> > adj;
ll root;
vector<ll> level; //starting in 0
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); level.pb(0);}
DFS_Build(r,r);
}
void DFS_Build(ll s, ll par)
{
if(s!=root) {level[s]=level[par]+1LL;}
p[s]=par;
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;
}
Tree Conv()
{
vector<vector<ll> > ad; vector<ll> xx; REP(i,0,N) {ad.pb(xx);}
Tree T(ad,root); return T;
vector<ll> values; REP(i,0,N) {values.pb(0LL);}
REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
Tree T(ad,root); T.val=values;
return T;
}
};
int travelTime(int n, int M, int L, int A[], int B[], int T[])
{
ll N = (ll) n;
vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
pl cur;
REP(i,0,M)
{
cur=mp(A[i],B[i]);
adj[cur.ff].pb(cur.ss); adj[cur.ss].pb(cur.ff);
}
unordered_map<pl,ll,hash_pair> w;
REP(i,0,M)
{
w[mp(A[i],B[i])]=T[i];
w[mp(B[i],A[i])]=T[i];
}
Graph G(adj);
vector<vector<ll> > H = G.CC();
vector<Tree> F;
REP(i,0,H.size())
{
vector<vector<pl> > ad; vector<pl> xxx; REP(j,0,H[i].size()) {ad.pb(xxx);}
unordered_map<ll,ll> t; REP(j,0,H[i].size()) {t[H[i][j]]=j;}
REP(j,0,H[i].size())
{
ll c = H[i][j];
REP(z,0,adj[c].size()) {ad[t[c]].pb(mp(t[adj[c][z]],w[mp(c,adj[c][z])]));}
}
WTree T(ad);
Tree T2 = T.Conv();
return 0;
F.pb(T2);
}
vector<ll> d; vector<ll> inner;
REP(i,0,F.size()) {F[i].Calc_Diametre(); d.pb(F[i].diametre.ff);}
sort(whole(d)); reverse(whole(d));
REP(i,0,F.size()) {F[i].Calc_farthest_down(F[i].root);}
REP(i,0,F.size()) {F[i].Calc_farthest_up(F[i].root);}
REP(i,0,F.size()) {F[i].Calc_farthest(); inner.pb(*min_element(whole(F[i].farthest)));}
sort(whole(inner)); reverse(whole(inner));
ll ans = d[0];
if(F.size()>=2) {ans=max(ans,inner[0]+inner[1]+L);}
if(F.size()>=3) {ans=max(ans,inner[1]+inner[2]+2LL*L);}
return ans;
}