Submission #1032754

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032754	2024-07-24T08:00:54 Z	vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;

constexpr int INF = 1e9;

// -----------------------------------------------------------------------------

int n, k;

struct edge {
	int v, w;
	edge() = default;
	edge(int v, int w): v(v), w(w) {}
};

vector<edge> g[N];

void add(int u, int v, int w) {
	g[u].emplace_back(v, w);
}

void Add(int u, int v, int w) {
	add(u, v, w), add(v, u, w);
}

int get_root(int);

// -----------------------------------------------------------------------------

int mp[M];

int vis[N], dis[N], dep[N];

int cnt, ans = INF;

void init(int u, int fa, int is, int ep) {
	if (is > k) return;
	++cnt;
	dis[cnt] = is, dep[cnt] = ep;
	for (auto t : g[u]) {
		if (t.v == fa || vis[t.v]) continue;
		init(t.v, u, is + t.w, ep + 1);
	}
}

void calc(int u) {
	mp[0] = cnt = 0;
	for (auto t : g[u]) {
		int v = t.v, w = t.w;
		if (vis[v]) continue;
		int st = cnt + 1;
		init(v, u, w, 1);
		for (int i = st; i <= cnt; ++i)
			ans = min(ans, mp[k - dis[i]] + dep[i]);
		for (int i = st; i <= cnt; ++i)
			mp[dis[i]] = min(mp[dis[i]], dep[i]);
	}
	for (int i = 1; i <= cnt; ++i) mp[dis[i]] = INF;
}

void solve(int u) {
	vis[u] = 1, calc(u);
	for (auto t : g[u]) {
		if (vis[t.v]) continue;
		solve(get_root(t.v));
	}
}

// -----------------------------------------------------------------------------

int siz[N], max_son[N];
int tot, root;

void dfs(int u, int fa) {
	siz[u] = 1, max_son[u] = 0;
	for (auto t : g[u]) {
		int v = t.v;
		if (v == fa || vis[v]) continue;
		dfs(v, u);
		siz[u] += siz[v];
		max_son[u] = max(max_son[u], siz[v]);
	}
	max_son[u] = max(max_son[u], tot - siz[u]);
	if (max_son[u] < max_son[root]) root = u;
}

int get_root(int u) {
	tot = siz[u], root = 0;
	return dfs(u, -1), root;
}

// -----------------------------------------------------------------------------

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k;
	memset(mp, 0x3f, sizeof mp);
	for (int i = 1; i < n; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		Add(u + 1, v + 1, w);
	}
	max_son[0] = n + 1;
	siz[1] = n;
	solve(get_root(1));
	cout << (ans >= n ? -1 : ans) << endl;
	return 0;
}

Compilation message

/usr/bin/ld: /tmp/ccxGHGnL.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvyndWK.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccvyndWK.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status