Submission #886409

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

race

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>
 
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define int ll
 
using namespace std;
 
const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e5 + 5;
const int MAXC = 1e6 + 5;

int n,k,sz[MAXN],ans = inf;
vector<pair<int,int>> adj[MAXN];
bool deleted[MAXN];
 
int get_subtree_sizes(int u,int p = 0) {
	sz[u] = 1;
	for (auto v : adj[u]) {
		if (!deleted[v.fi] && v.fi != p) {
			sz[u] += get_subtree_sizes(v.fi,u);	
		}
	}
	return sz[u];
}
 
int find_centroid(int desired,int u,int p = 0) {
	for (auto v : adj[u]) {
		if (v.fi != p && !deleted[v.fi] && sz[v.fi] >= desired) {
			return find_centroid(desired,v.fi,u);
		}
	}
	return u;
}
 
unordered_map<int,int> mp;
vector<pair<int,int>> update;
int mx_len,cnt[MAXC];
 
void dfs(int u,int p,int len,int depth) {
	if (len > k) return;
	if (cnt[k - len] != -1) {
		ans = min(ans,cnt[k - len] + depth);
	}
	mx_len = max(mx_len,len);
	update.emplace_back(len,depth);
	for (auto v : adj[u]) {
		if (v.fi != p && !deleted[v.fi]) {
			dfs(v.fi,u,len + v.se,depth + 1);
		}
	}
}
 
void solve(int u) {
	int centroid = find_centroid(get_subtree_sizes(u) >> 1,u);	
	cnt[0] = 0;
	mx_len = 0;
	for (auto v : adj[centroid]) {
		if (deleted[v.fi]) continue;
		// solve for v
		dfs(v.fi,centroid,v.se,1);
		for (auto x : update) {
			if (cnt[x.fi] == -1) cnt[x.fi] = x.se;
			else cnt[x.fi] = min(cnt[x.fi],x.se);
		}
		// update for v
		update.clear();
	}
	fill(cnt,cnt + mx_len + 1,-1);
	deleted[centroid] = true;
	for (auto v : adj[centroid]) {
		if (!deleted[v.fi]) {
			solve(v.fi);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N,k = K;
	for (int i = 0;i < n - 1;i++) {
		adj[H[i][0] + 1].emplace_back(H[i][1] + 1,L[i]);
		adj[H[i][1] + 1].emplace_back(H[i][0] + 1,L[i]);
	}
	solve(1);
	if (ans > n) return -1;
	else return ans;
}
// agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

/usr/bin/ld: /tmp/ccK079YJ.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