Submission #599089

#	Time	Username	Problem	Language	Result	Execution time	Memory
599089		acatmeowmeow	Race (IOI11_race)	C++11	0 / 100	16 ms	28496 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int NMAX = 2e5 + 5, LG = 20;
// binary lifting
vector<pair<int, int>> adj1[NMAX];
int tin[NMAX], tout[NMAX], timer = 0, anc[NMAX][LG + 5], d[NMAX], h[NMAX];

void dfs1(int u, int e) {
	if (u) anc[u][0] = e;
	for (int i = 1; i <= LG; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
	for (auto&x : adj1[u]) { 
		int v = x.first, c = x.second;
		if (v == e) continue;
		d[v] = d[u] + c, h[v] = h[u] + 1;
		dfs1(v, u);
	}
}

int lca(int u, int v) {
	if (h[u] < h[v]) swap(u, v);
	int d = h[u] - h[v];
	for (int i = 0; i <= LG; i++) { if (d & (1ll << i)) u = anc[u][i]; }
	if(u == v) return u;
	for (int i = LG; i >= 0; i--) { if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i]; }
	return anc[u][0];
}

int path_cost(int u, int v) { return d[u] + d[v] - 2*d[lca(u, v)]; }

int path_edge(int u, int v) { return h[u] + h[v] - 2*h[lca(u, v)]; }

// centroid decomposition
set<int> adj2[NMAX];
int p[NMAX], sz[NMAX];

int dfs2(int u, int e) {
	sz[u] = 1;
	for (auto&v : adj2[u]) {
		if (v == e) continue;
		sz[u] += dfs2(v, u);
	}
	return sz[u];
}

int dfs3(int u, int e, int s) {
	for (auto&v : adj2[u]) { if (v != e && sz[v] > s/2) return dfs3(v, u, s); }
	return u;
}

void build(int u, int e) {
	int s = dfs2(u, e), centroid = dfs3(u, e, s);
	p[centroid] = e;
	set<int> cur = adj2[centroid];
	for (auto&v : cur) {
		adj2[centroid].erase(v), adj2[v].erase(centroid);
		build(v, centroid);
	}
}
// solve the problem
vector<int> adj3[NMAX];

void init(int N) {
	for (int i = 0; i < N; i++) { 
		if (p[i] == -1) continue;
		adj3[i].push_back(p[i]), adj3[p[i]].push_back(i);
	}
}

map<int, int> mn[NMAX];
int ans = 1e18;

void solve(int u, int e, int K) {
	for (int v = u; v != -1; v = p[v]) {
		int cost = path_cost(u, v), edge = path_edge(u, v);
		if (mn[v].count(K - cost)) {
			ans = min(ans, edge + mn[v][K - cost]);
			cout << u << ' ' << v << ' ' << edge << ' ' << mn[v][K - cost] << '\n';
		}
		if (!mn[v].count(cost)) mn[v][cost] = 1e18;
		mn[v][cost] = min(mn[v][cost], edge);
	}
	for (auto&v : adj3[u]) {
		if (v == e) continue;
		solve(v, u, K);
	}
}

signed best_path(signed N, signed K, signed H[][2], signed L[]) {
	for (int i = 0; i < N - 1; i++) {
		int u = H[i][0], v = H[i][1], c = L[i];
		adj1[u].push_back({v, c}), adj1[v].push_back({u, c});
		adj2[u].insert(v), adj2[v].insert(u);
	}
	dfs1(0, -1);
	build(0, -1);
	init(N);
	solve(0, -1, K);
	return ans == 1e18 ? -1 : ans;
}

/*int N, K, H[NMAX][2], L[NMAX];

signed main() {
	cin >> N >> K;
	for (int i = 0; i < N - 1; i++) cin >> H[i][0] >> H[i][1] >> L[i];
	cout << best_path(N, K, H, L) << '\n'; 
	return 0;
}*/

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