Submission #203912

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

race

#include <bits/stdc++.h>
#include <random>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;

const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;

int n, k, ans = INF;
int siz[202020], chk[202020];
vector<pii> adj[202020];

int find_size(int x, int par) {
	int ret = 1;
	for (auto th : adj[x]) {
		if (th.first == par || chk[th.first]) continue;
		ret += find_size(th.first, x);
	}
	return siz[x] = ret;
}

int get_cent(int x, int par, int cnt) {
	for (auto th : adj[x]) {
		if (th.first == par || chk[th.first]) continue;
		if (siz[th.first] > cnt / 2) return get_cent(th.first, x, cnt);
	}
	return x;
}

vector<pii> all_path;
void find_path(int x, int par, int len, int dep) {
	if (len > k) return;
	all_path.emplace_back(len, dep);
	for (auto th : adj[x]) {
		if (th.first == par || chk[th.first]) continue;
		find_path(th.first, x, len + th.second, dep + 1);
	}
}

void solve(int x) {
	int cal = find_size(x, x);
	int cent = get_cent(x, x, cal);

	// cent를 지나는 경로들
	all_path.clear();
	find_path(cent, cent, 0, 0);
	sort(all(all_path));

	vector<pii> path;
	for (auto hr : all_path) {
		if (!path.empty() && path.back().first == hr.first) continue;
		path.push_back(hr);
	}

	int ri = sz(path) - 1;
	for (int i = 0; i < ri; i++) {
		int left = k - path[i].first;
		while (ri > i + 1 && path[ri].first > left) ri--;
		if (path[ri].first == left)
			ans = min(ans, path[i].second + path[ri].second);
	}

	// cent를 지나지 않는 경로들
	chk[cent] = 1;
	for (auto th : adj[cent]) {
		int thv = th.first;
		if (chk[thv]) continue;
		solve(thv);
	}
}

int best_path(int N, int K, vector<vector<int> > H, vector<int> L) {
	n = N; k = K;
	for (int i = 0; i < sz(H); i++) {
		int a = H[i][0], b = H[i][1];
		adj[a].emplace_back(b, L[i]);
		adj[b].emplace_back(a, L[i]);
	}
	solve(0);
	if (ans == INF) return -1;
	else return ans;
}

Compilation message (stderr)

/tmp/cc4OOj4N.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