Submission #24040

#	Time	Username	Problem	Language	Result	Execution time	Memory
24040		Nirjhor	Dreaming (IOI13_dreaming)	C++14	100 / 100	113 ms	14620 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

typedef pair <int, int> edge;

#define to first
#define cost second

const int MAX = 123456;

bitset <MAX> vis;
vector <edge> g[MAX];
int maxDist, at;
edge par[MAX];

void dfs (int u, int from, int far, int flag) {
	if (flag) {
		vis[u] = 1;
	}
	if (far > maxDist) {
		maxDist = far;
		at = u;
	}
	for (edge e : g[u]) {
		if (e.to == from) continue;
		if (flag) {
			par[e.to] = edge(u, e.cost);
		}
		dfs(e.to, u, far + e.cost, flag);
	}
}

int travelTime (int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 0; i < M; ++i) {
		g[A[i]].emplace_back(B[i], T[i]);
		g[B[i]].emplace_back(A[i], T[i]);
	}
	
	vector <int> R;
	int ret = 0;
	for (int i = 0; i < N; ++i) {
		if (vis[i]) continue;
		maxDist = -1;
		dfs(i, i, 0, 0);
		int one = at;
		maxDist = -1;
		dfs(one, one, 0, 1);
		int two = at;
		
		ret = max(ret, maxDist);
		
		int half = maxDist >> 1;
		int radius = 0;
		for (int v = two; v != one; v = par[v].to) {
			if (radius + par[v].cost > half) {
				radius = min(radius + par[v].cost, maxDist - radius);
				break;
			}
			radius += par[v].cost;
		}
		R.push_back(radius);
	}

	sort(R.rbegin(), R.rend());
	if (R.size() > 1) ret = max(ret, R[0] + R[1] + L);
	if (R.size() > 2) ret = max(ret, R[1] + R[2] + L + L);
	return ret;
}

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