제출 #846565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846565		midi	꿈 (IOI13_dreaming)	C++14	18 / 100	308 ms	32196 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 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>>4ll)
#define mxN 100'010ll

ll n, m, l;
int *uar, *var, *war;
vc<vc<prll>> gr(mxN); // fi is w, se is v
vcll ar;

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

		gr[u].pb({w, v});
		gr[v].pb({w, u});
	}
}

vc<bool> seen(mxN, 0);
map<prll, ll> from_to; // the "to" gives the value

inline void init_umap()
{
	ll u;
	f0r(u,0,n)
	{
		from_to[mp(-1,u)]=-1;
		for (prll edge : gr[u])
		{
			ll v = edge.se;
			from_to[mp(u,v)]=-1;
			from_to[mp(v,u)]=-1;
		}
	}
}

vcll comp; // comp for component

void dfs(ll u)
{
	if (seen[u]) return;
	// printf("real, u: %lli\n", u);
	seen[u]=1;
	comp.pb(u);
	for (prll edge : gr[u])
	{
		ll v=edge.se;
		dfs(v);
	}
}

ll calc_from_to(ll p, ll u)
{
	ll &t = from_to[mp(p,u)];
	// if (t!=-1) printf("p: %lli, u: %lli, t: %lli\n", p, u, t);
	if (t!=-1) return t;

	ll m=0; // max
	for (prll edge : gr[u])
	{
		ll v=edge.se;
		if (v==p) continue;
		ll w=edge.fi;

		maxa(m, calc_from_to(u,v)+w);
	}

	// printf("res: %lli\n", m);
	return t=m;
}

inline ll minmaxdist(ll u)
{
	comp.clear();
	dfs(u);
	// printf("comp.size: %lli\n", (ll)comp.size());

	ll m=INF; // min
	for (ll u : comp)
	{
		mina(m, calc_from_to(-1, u));
		// printf("min: %lli\n", m);
	}
	// printf("true\n");

	return m;
}

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

inline ll value()
{
	ll z=ar.size();
	// printf("z: %lli\n", z);
	if (z==1) return ar[0];
	if (z==2) return ar[0]+ar[1]+l;

	return max(ar[0]+ar[1]+l, ar[1]+ar[2]+(2*l));
}

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();
	sort(allrev(ar));
	return value();
}

/*
int main()
{
	freopen("dreaming.in", "r", stdin);

	int N, M, L, *A, *B, *T;
	A=new int[mxN];
	B=new int[mxN];
	T=new int[mxN];
	cin >> N >> M >> L;
	ll i;
	f0r(i,0,M) cin >> A[i] >> B[i] >> T[i];

	int v = travelTime(N, M, L, A, B, T);

	printf("ans: %i\n", v);

	return 0;
}
*/

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