Submission #302263

#	Time	Username	Problem	Language	Result	Execution time	Memory
302263		nhdtxdy	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define eb emplace_back
#define Size(v) (int)v.size()
using namespace std;

// Always
const int nax = 2e5 + 5, INF = 1e9 + 7;
int n, k;
vector<pair<int, int>> adj[nax];
map<int, int> vec[nax];
int dist[nax], ans[nax], sz[nax], dep[nax];

void getsz(int v, int p = 0) {
	sz[v] = 1;
	for (auto &q : adj[v]) {
		int c = q.first, w = q.second;
		if (c == p) continue;
		dep[c] = dep[v] + 1;
		dist[c] = dist[v] + w;
		getsz(c, v);
		sz[v] += sz[c];
	}
}

void dfs(int v, int p = 0, bool keep = false) {
	int maxi = -1, bigchild = -1;
	for (auto &q : adj[v]) {
		int u = q.first;
		if (u == p) continue;
		if (maxi < sz[u]) {
			maxi = sz[u];
			bigchild = u;
		}
	}
	for (auto &q : adj[v]) {
		int u = q.first;
		if (u == p || u == bigchild) continue;
		dfs(u, v, false);
	}
	if (bigchild != -1) {
		dfs(bigchild, v, true);
		swap(vec[v], vec[bigchild]);
	}

	vec[v][dist[v]] = dep[v];	
	int subtract = dist[v];

	if (vec[v].find(k + dist[v]) != vec[v].end()) {
		ans[v] = min(ans[v], vec[v][k + dist[v]] - dep[v]);
	}

	int target = k + 2 * subtract;
	// if (v == 1) {
	// 	cout << "v == 1\n";
	// 	cout << "target: " << target << '\n';
	// }
	for (auto &q : adj[v]) {
		int c = q.first;
		if (c == p || c == bigchild) continue;
		if (vec[c].find(k + dist[v]) != vec[c].end()) {
			ans[v] = min(ans[v], vec[c][k + dist[v]] - dep[v]);
		}
		for (auto &u : vec[c]) {
			if (vec[v].find(target - u.first) != vec[v].end()) {
				ans[v] = min(ans[v], u.second + vec[v][target - u.first] - 2 * dep[v]);
			}
		}
		for (auto &u : vec[c]) {
			if (vec[v].find(u.first) != vec[v].end()) vec[v][u.first] = min(vec[v][u.first], u.second);
			else vec[v][u.first] = u.second;
		}
	}
	
	// cout << "v: " << v << '\n';
	// for (auto &p : vec[v]) {
	// 	cout << p.first << ' ' << p.second << '\n';
	// }
	// cout << "end v" << '\n';
}

int best_path(int x, int y, vector<vector<int>> h, vector<int> l) {
	fill(ans, ans + nax, INF);
	n = x;
	k = y;
	for (int i = 0; i < Size(h); ++i) {
		int u = h[i][0], v = h[i][1];
		++u, ++v;
		cerr << u << ' ' << v << ' ' << l[i] << '\n';
		adj[u].eb(v, l[i]);
		adj[v].eb(u, l[i]);
	}
	getsz(1);
	// for (int i = 1; i <= n; ++i) cout << sz[i] << ' ';
	// cout << '\n';
	dfs(1);
	int res = INF;
	// for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
	// cout << '\n';
	for (int i = 1; i <= n; ++i) res = min(res, ans[i]);
	return res;
}

void test() {
	cerr << "test\n";
	int n = 11, k = 12;
	vector<vector<int>> h = 
	{
		{0, 1},
		{0, 2},
		{2, 3},
		{3, 4},
		{4, 5},
		{0, 6},
		{6, 7},
		{6, 8},
		{8, 9},
		{8, 10}
	};
	vector<int> l = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
	cout << best_path(n, k, h, l);
}

Compilation message (stderr)

/tmp/ccFlFLGz.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status