제출 #852465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852465		midi	꿈 (IOI13_dreaming)	C++14	40 / 100	115 ms	65536 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll, ll> prll;
#define umap unordered_map

#define f0r(i,a,n) for (i=(a); i<(n); i++)
#define f1r(i,a,n) for (i=(a); i<=(n); i++)
#define r0f(i,n,a) for (i=(n); i>(a); i--)
#define r1f(i,n,a) for (i=(n); i>=(a); i--)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define in(s, x) ((s).find((x)) != (s).end())
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

#define INF (LLONG_MAX>>2ll)
#define mxN 100'010ll

ll n, m, l;
int *uar, *var, *war;
vc<vc<prll>> gr(mxN); // fi is w, se is v
vc<prll> par(mxN);
vc<vcll> from_tar(mxN); // .back() is for the parent
vc<umap<ll, ll>> nindex(mxN); // index of node in the gr, from_tar, excetera
vcll f;

inline void build_gr()
{
	ll i;
	f0r(i,0,m)
	{
		ll u, v, w;
		u=uar[i];
		v=var[i];
		w=war[i];

		nindex[u][v] = gr[u].size();
		nindex[v][u] = gr[v].size();
		gr[u].pb({w, v});
		gr[v].pb({w, u});
		from_tar[u].pb(-1);
		from_tar[v].pb(-1);
	}
}

vc<bool> seen(mxN, 0);
vcll whole(mxN); // whole

vcll comp; // comp for component

void dfs(ll u) // makes tree // good
{
	if (seen[u]) return;
	seen[u]=1;
	comp.pb(u);
	for (prll edge : gr[u])
	{
		ll v=edge.se;
		if (seen[v]) continue; // is par
		ll w=edge.fi;
		par[v]={w, u};
		dfs(v);
	}
}

ll calc_cnt=0;
ll clutch_cnt=0;

ll calc_whole(ll u)
{
	ll m=0; // max

	for (prll edge : gr[u])
	{
		ll v=edge.se;
		ll w = edge.fi;
		maxa(m, calc_whole(v) + w);
	}

	return whole[u]=m;
}

vc<umap<ll, ll>> max_except(mxN);

void build_except(ll u, vc<prll> &ar) // fi is node, se is max
{
	ll i;
	ll n=ar.size();

	/*
	printf("bulid_except of u: %lli\n", u);
	printf("ar: ");
	f0r(i,0,n) printf("{%lli, %lli} ", ar[i].se, ar[i].fi);
	printf("\n");
	*/

	vcll sma(n+10); // max, incl., sma[n]==0
	sma[n]=0;
	r1f(i,n-1, 0) sma[i]=max(sma[i+1], ar[i].fi);
	/*
	printf("sma: ");
	f0r(i,0,n) printf("%lli ", sma[i]);
	printf("\n");
	*/

	ll rm=0; // running max

	f0r(i,0,n)
	{
		max_except[u][ar[i].se] = max(rm, sma[i+1]);
		// printf("rm: %lli\n", rm);
		// printf("value of %lli: %lli\n", ar[i].se, max(rm, sma[i+1]));
		maxa(rm, ar[i].fi);
	}

	sma.clear();
}

void build_ar_root(ll u)
{
	vc<prll> ar;
	for (prll edge : gr[u])
	{
		ll v=edge.se;
		ll w=edge.fi;
		ar.pb({whole[v]+w, v});
	}

	build_except(u, ar);
	ar.clear();
}

ll root;
ll gm;

ll dfs_calc_real(ll u)
{
	ll m=whole[u]; // max
	if (u==root)
	{
		for (prll edge : gr[u])
		{
			ll v = edge.se;
			mina(gm, dfs_calc_real(v));
		}

		return m;
	}

	// u!=root
	
	vc<prll> ar;
	
	for (prll edge : gr[u])
	{
		ll v = edge.se;
		ll w = edge.fi;
		ar.pb({whole[v]+w, v});
	}
	ll p=par[u].se;
	ll w=par[u].fi;
	ll v = max_except[p][u];
	maxa(whole[u], w+v);
	ar.pb({w+v, p});
	m=whole[u];

	build_except(u, ar);
	ar.clear();

	for (prll edge : gr[u])
	{
		ll v = edge.se;
		mina(gm, dfs_calc_real(v));
	}

	return m;
}

inline void remake_gr()
{
	for (ll u : comp) for (prll &edge : gr[u])
		{
			ll v=edge.se;
			if (par[u].se==v)
			{
				edge=gr[u][gr[u].size()-1];
				gr[u].pop_back();
			}
		}
}

inline ll minmaxdist(ll u)
{
	comp.clear();
	root=u;
	par[root]={0, -1};
	dfs(u); // good
	remake_gr(); // bad
	// printf("comp.size: %lli\n", (ll)comp.size());
	
	calc_whole(u); // prob works
	build_ar_root(u);

	gm=INF;
	ll t = dfs_calc_real(u); // min
	mina(gm, t);

	// printf("m: %lli, on u: %lli\n", m, u);

	return gm;
}

inline void build_ar()
{
	ll u;
	f0r(u,0,n)
	{
		if (seen[u]) continue;
		// printf("WPAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA, u: %lli\n", u);
		f.pb(minmaxdist(u));
	}
}

inline ll value()
{
	ll z=f.size();
	ll m=-1; // max
	/*
	printf("z: %lli\n", z);
	printf("f: ");
	for (ll v : f) printf("%lli ", v);
	printf("\n");
	*/

	if (z==1) m = f[0];
	else if (z==2) m = f[0]+f[1]+l;
	else m = max(f[0]+f[1]+l, f[1]+f[2]+(2*l));

	ll u;
	f0r(u,0,n) maxa(m, whole[u]);
	return m;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	n=N;
	m=M;
	l=L;
	uar=A;
	var=B;
	war=T;

	build_gr();
	build_ar(); // slow
	sort(allrev(f));
	return value();
}

• Subtask 1: 0 / 14
• Subtask 2: 10 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23