Submission #986644

#	Time	Username	Problem	Language	Result	Execution time	Memory
986644		happypotato	Race (IOI11_race)	C++17	0 / 100	6 ms	16728 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 2e5 + 10;
vector<pii> adj[mxN];
bool vis[mxN];
int subt[mxN], dep[mxN];
int centpar[mxN];
ll path[mxN];
map<ll, vector<pii>> mp[mxN];
void dfs_subt(int u, int par) {
	subt[u] = 1;
	for (pii v : adj[u]) {
		if (v.ff == par || vis[v.ff]) continue;
		dfs_subt(v.ff, u);
		subt[u] += subt[v.ff];
	}
}
int dfs_cent(int u, int par, int tar) {
	for (pii v : adj[u]) {
		if (v.ff == par || vis[v.ff]) continue;
		if (subt[v.ff] * 2 > tar) return dfs_cent(v.ff, u, tar);
	}
	return u;
}
void dfs_decomp(int u = 1, int par = 0, int depth = 1) {
	dfs_subt(u, par);
	u = dfs_cent(u, par, subt[u]);
	dep[u] = depth;
	centpar[u] = par;
	vis[u] = true;
	for (pii v : adj[u]) {
		if (v.ff == par || vis[v.ff]) continue;
		dfs_decomp(v.ff, u, depth + 1);
	}
}
void dfs_path(int u = 1, int par = 0, ll cur = 0) {
	path[u] = cur;
	for (pii v : adj[u]) {
		if (v.ff == par) continue;
		dfs_path(v.ff, u, cur + v.ss);
	}
}
int best_path(int n, int k, int H[][2], int L[]) {
	for (int i = 0; i < n; i++) {
		H[i][0]++; H[i][1]++;
		adj[H[i][0]].pb({H[i][1], L[i]});
		adj[H[i][1]].pb({H[i][0], L[i]});
	}
	dfs_decomp();
	dfs_path();

	vector<int> order;
	for (int i = 1; i <= n; i++) order.pb(i);
	sort(order.begin(), order.end(), [&](int x, int y) {
		return dep[x] > dep[y];
	});
	int ans = n;
	for (int x : order) {
		// cerr << x << ":\n";
		// for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
		// 	cerr << it->ff << " | ";
		// 	for (pii cur : it->ss) {
		// 		cerr << "{" << cur.ff << ", " << cur.ss << "} ";
		// 	}
		// 	cerr << endl;
		// }
		// cerr << "end of " << x << endl;

		for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
			sort(it->ss.begin(), it->ss.end());
		}
		if (mp[x].find(path[x] + k) != mp[x].end()) {
			ans = min(ans, mp[x][path[x] + k].front().ff - dep[x]);
		}
		for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
			ll tar = path[x] * 2 - it->ff + k;
			if (mp[x].find(tar) != mp[x].end()) {
				for (pii cur : mp[x][tar]) {
					if (cur.ss == it->ss.front().ss) continue;
					ans = min(ans, cur.ss + it->ss.front().ff - 2 * dep[x]);
					break;
				}
			}
		}
		if (x == 1) break;
		mp[x][path[x]] = {{dep[x], x}};
		for (auto it = mp[x].begin(); it != mp[x].end(); ++it) {
			mp[centpar[x]][it->ff].pb({it->ss.front().ff, x});
		}
	}
	return (ans == n ? -1 : ans);
}

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