Submission #341640

#	Time	Username	Problem	Language	Result	Execution time	Memory
341640		Drew_	Dreaming (IOI13_dreaming)	C++14	100 / 100	167 ms	17644 KiB

dreaming

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

#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second

int const inf = 1e9 + 7;

vector<vector<ii>> adj;
vector<ii> dst; //furthest and second furthest distance from vertex
vector<bool> vst;
vector<int> vertices;

inline ii combine(ii x, int y)
{
	int a = max(max(x.f1, x.s2), y);
	int b = x.f1 + x.s2 + y - a - min(min(x.f1, x.s2), y);

	return {a, b};
}

void dfs(int node)
{
	vst[node] = true;
	vertices.pb(node);
	for (ii to : adj[node])
	{
		if (!vst[to.f1])
		{
			dfs(to.f1);
			dst[node] = combine(dst[node], to.s2 + dst[to.f1].f1);
		}
	}
}

void reroot(int node)
{
	vst[node] = true;
	for (ii to : adj[node])
	{
		if (!vst[to.f1])
		{
			if (dst[node].f1 == to.s2 + dst[to.f1].f1)
				dst[to.f1] = combine(dst[to.f1], to.s2 + dst[node].s2);
			else dst[to.f1] = combine(dst[to.f1], to.s2 + dst[node].f1);

			reroot(to.f1);
		}
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	adj.resize(N);
	dst.assign(N, {0, 0});
	vst.assign(N, false);

	for (int i = 0; i < M; ++i)
		adj[A[i]].pb({B[i], T[i]}), adj[B[i]].pb({A[i], T[i]});

	vector<int> candidate; //vertice connecting with other tree
	for (int i = 0; i < N; ++i)
	{
		if (!vst[i])
		{
			vertices.clear();
			dfs(i);

			for (int x : vertices)
				vst[x] = false;
			reroot(i);

			int best = vertices[0];
			for (int x : vertices)
			{
				if (dst[best].f1 > dst[x].f1)
					best = x;
			}
			candidate.pb(best);
		}
	}

	int best = candidate[0];
	for (int x : candidate)
	{
		//cerr << x << ": " << dst[x].f1 << '\n';
		if (dst[best].f1 < dst[x].f1)
			best = x;
	}

	for (int x : candidate)
	{
		if (best != x)
			adj[best].pb({x, L}), adj[x].pb({best, L});
	}

	dst.assign(N, {0, 0});
	vst.assign(N, false);
	dfs(0);

	vst.assign(N, false);
	reroot(0);

	int res = 0;
	for (int i = 0; i < N; ++i)
		res = max(res, dst[i].f1);

	return res;
}

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