Submission #706471

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

race

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
//#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353
const int inf = 1e9 + 1;

int n, k;
vector<pii> adj[MAX_N];
bool processed[MAX_N];
int ans = inf;
int child[MAX_N];

int dfs(int u, int pr = 0) {
	child[u] = 1;
	for (auto it : adj[u]) {
		int v = it.fi;
		if (!processed[v] && v != pr) {
			child[u] += dfs(v, u);
		}
	}
	return child[u];
}

int find_centroid(int u, int pr, int sz) {
	for (auto it : adj[u]) {
		int v = it.fi;
		if (!processed[v] && v != pr && child[v] > sz) {
			return find_centroid(v, u, sz);
		}
	}
	return u;
}

const int MAX_VAL = 1e6 + 10;
int dp[MAX_VAL];
vector<int> used;

void go_cal(int u, int pr, bool ok, int len, int dep) {
	if (k < len) return;

	if (ok) {
		used.pb(len);
		minimize(dp[len], dep);
	}
	else {
		minimize(ans, dp[k - len] + dep);
	}

	for (auto it : adj[u]) {
		int v = it.fi;
		int w = it.se;
		if (!processed[v] && v != pr) {
			go_cal(v, u, ok, len + w, dep + 1);
		}
	}
}

void centroid_decomposition(int u) {
	int c = find_centroid(u, 0, dfs(u) >> 1);
	processed[c] = true;

	used.clear();

	dp[0] = 0;

	for (auto it : adj[c]) {
		int v = it.fi;
		int w = it.se;
		if (!processed[v]) {
			go_cal(v, c, false, w, 1);
			go_cal(v, c, true, w, 1);
		}
	}

	for (auto it : used) {
		dp[it] = inf;
	}

	for (auto it : adj[c]) {
		int v = it.fi;
		if (!processed[v]) {
			centroid_decomposition(v);
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> k;
	for (int i = 0; i <= k; i ++) {
		dp[i] = inf;
	}
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u++; v++;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}

	centroid_decomposition(1);

	cout << (ans == inf ? -1 : ans);

	return 0;
}

/*


*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccehc9pE.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYNsxRB.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYNsxRB.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