Submission #331129

#	Time	Username	Problem	Language	Result	Execution time	Memory
331129		prarie	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define fi first
#define se second
#define endl '\n'
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compress(v) sort(all(v)), (v).erase(unique(all((v))), v.end())
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
 
const int N = 2e5 + 5;
const int K = 1e6 + 5;

int n, k;
vector<pii> adj[N];
bool fin[N];
int sz[N];
int d[K];

int get_cent(int t_size, int cur, int pv = -1) {
	int minx = N;
	int ret = -1;
	for (auto &next : adj[cur]) {
		if (pv == next.first || fin[next.first]) continue;
		if (sz[next.first] > t_size / 2)
			return get_cent(t_size, next.first, cur);
		minx = min(minx, sz[next.first]);
	}
	if (minx <= t_size / 2) return cur;
	return -1;
}

void get_sz(int cur, int pv = -1) {
	sz[cur] = 1;
	for (auto &next : adj[cur]) {
		if (next.first == pv || fin[next.first]) continue;
		get_sz(next.first, cur);
		sz[cur] += sz[next.first];
	}
}

void assign(int cur, int w, int pv = -1, int cnt = 1) {
	if (w > k) return;
	d[w] = min(d[w], cnt);
	for (auto &next : adj[cur]) {
		if (next.first == pv || fin[next.first]) continue;
		assign(next.first, next.second + w, cur, cnt + 1);
	}
}

int get(int cur, int w, int pv = -1, int cnt = 1) {
	int ret = N;
	if (w > k) return ret;
	ret = min(ret, cnt + d[k - w]);
	for (auto &next : adj[cur]) {
		if (next.first == pv || fin[next.first]) continue;
		ret = min(get(next.first, w + next.second, cur, cnt + 1), ret);
	}
	return ret;
}

int calc(int node) {
	int ret = N;
	// Find Centroid
	memset(sz, 0, sizeof sz);
	get_sz(node);
	int cent = get_cent(sz[node], node);
	if (cent == -1) {
		fin[node] = true;
		return ret;
	}

	fin[cent] = true;

	// Find Minimum nodes of length K
	memset(d, 0x3f, sizeof d);
	d[0] = 0;
	for (auto &next : adj[cent]) {
		if (fin[next.first]) continue;
		ret = min(ret, get(next.first, next.second));
		assign(next.first, next.second);
	}

	// call calc for subtrees
	for (auto &next : adj[cent]) {
		if (fin[next.first]) continue;
		ret = min(ret, calc(next.first));
	}
	return ret;
}

int main() {
	fastio;
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	cout << calc(0) << endl;
}

Compilation message (stderr)

race.cpp: In function 'int get_cent(int, int, int)':
race.cpp:29:6: warning: unused variable 'ret' [-Wunused-variable]
   29 |  int ret = -1;
      |      ^~~
/tmp/ccuzNaRD.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccPeprGp.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccPeprGp.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status