Submission #654503

#	Time	Username	Problem	Language	Result	Execution time	Memory
654503		adaawf	경주 (Race) (IOI11_race)	C++14	100 / 100	1472 ms	75248 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> g[300005], a;
int n, k, c[300005], dd[300005], res = 999999999;
int dfs(int x, int p) {
	c[x] = 1;
	for (auto w : g[x]) {
		if (w[0] != p && dd[w[0]] == 0) {
            c[x] += dfs(w[0], x);
		}
	}
	return c[x];
}
void dfs2(int x, int p, int v, int num, int d) {
	for (auto w : g[x]) {
		if (w[0] != p && dd[w[0]] == 0) {
            dfs2(w[0], x, v + w[1], num + 1, d);
		}
	}
	a.push_back({v, num, d});
}
int centroid(int x, int sz, int p) {
	for (auto w : g[x]) {
		if (w[0] != p && dd[w[0]] == 0 && c[w[0]] * 2 > sz) {
			return centroid(w[0], sz, x);
		}
	}
	return x;
}
void trya(int x, int p) {
	int c = centroid(x, dfs(x, -1), -1), d = 0;
	a.clear();
	for (auto w : g[c]) {
		if (dd[w[0]] == 0) {
            dfs2(w[0], c, w[1], 1, d);
		}
		a.push_back({0, 0, d});
		d++;
	}
	sort(a.begin(), a.end());
	int l = 0, r = a.size() - 1;
	while (l <= r) {
		if (a[l][0] + a[r][0] > k) {
			r--;
		}
		else if (a[l][0] + a[r][0] == k) {
			if (a[l][2] == a[r][2]) {
				if (a[r][0] != a[r - 1][0]) {
					l++;
					continue;
				}
				r--;
				continue;
			}
			else {
				res = min(res, a[l][1] + a[r][1]);
				r--;
			}
		}
		else if (a[l][0] + a[r][0] < k) {
			l++;
		}
	}
	dd[c] = 1;
	for (auto w : g[c]) {
		if (dd[w[0]] == 0) {
            trya(w[0], c);
		}
	}
}
int best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	k = K;
	for (int i = 0; i < n - 1; i++) {
		g[H[i][0]].push_back({H[i][1], L[i]});
		g[H[i][1]].push_back({H[i][0], L[i]});
	}
	trya(0, -1);
	if (res == 999999999) return -1;
	return res;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57