제출 #339264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339264		penguinhacker	경주 (Race) (IOI11_race)	C++14	43 / 100	3097 ms	46060 KiB

race

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

#define ll long long
#define ar array

const int mxN = 200000;
int n, k, ans, sz[mxN];
bool dead[mxN];
vector<pair<int, int>> adj[mxN];

int dfs_sz(int u, int p) {
	sz[u] = 1;
	for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first])
		sz[u] += dfs_sz(v.first, u);
	return sz[u];
}

int get_centroid(int u, int p, int tree_sz) {
	for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first] && 2 * sz[v.first] > tree_sz)
		return get_centroid(v.first, u, tree_sz);
	return u;
}

map<pair<int, int>, int> mp, mp2;
void dfs(int u, int p, int d, int wd, int inc, map<pair<int, int>, int>& m) {
	if (wd > k) return;
	m[{wd, d}] += inc;
	if (m[{wd, d}] == 0) {
		m.erase({wd, d});
	}
	for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first]) {
		dfs(v.first, u, d + 1, wd + v.second, inc, m);
	}
}

void centroid(int u = 0) {
	u = get_centroid(u, -1, dfs_sz(u, -1));
	dead[u] = 1;
	dfs(u, -1, 0, 0, 1, mp);
	for (pair<int, int> v : adj[u]) if (!dead[v.first]) {
		dfs(v.first, u, 1, v.second, -1, mp);
		dfs(v.first, u, 1, v.second, 1, mp2);
		for (auto& x : mp2) {
			pair<int, int> p = x.first;
			int other = k - p.first;
			auto it = mp.lower_bound({other, -1});
			if (it != mp.end() && it->first.first == other) {
				ans = min(ans, p.second + it->first.second);
			}
		}
		dfs(v.first, u, 1, v.second, 1, mp);
		mp2.clear();
	}
	mp.clear();
	for (pair<int, int> v : adj[u]) if (!dead[v.first]) {
		centroid(v.first);
	}
	dead[u] = 0;
}

int best_path(int _n, int _k, int h[][2], int l[]) {
	n = _n, k = _k, ans = INT_MAX;
	for (int i = 0; i < n - 1; ++i) {
		int u = h[i][0], v = h[i][1], w = l[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	centroid();
	if (ans == INT_MAX) ans = -1;
	return ans;
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	int h[n - 1][2];
	int l[n - 1];
	for (int i = 0; i < n - 1; ++i) {
		cin >> h[i][0] >> h[i][1];
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> l[i];
	}
	cout << best_path(n, k, h, l);
	return 0;
}
*/

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