Submission #456361

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

race

#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define ii pair<int, int>
#define ll long long

int N, K, ans, cnt[1000100], subSize[MAXN], root[MAXN];
vector<ii> adj[MAXN];


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	

}

int best_path(int n, int k, int H[][2], int L[]) {
	N = n;
	K = k;
	for (int i = 0, u, v; i < N - 1; i++) {
		u = H[i][0];
		v = H[i][1];
		adj[u].push_back(ii(v, L[i]));
		adj[v].push_back(ii(u, L[i]));

	}
	ans = -1;
	memset(cnt, -1, sizeof(cnt));
	centroid();
	return ans;
}

void del(int sum, int cur, int par = -1) {
	if (sum > K) return;
	cnt[sum] = -1;
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (next != par && !root[next]) {
			del(sum + cost, next, cur);
		}
	}
}


int centroid(int cur = 0) {
	cur = get_centroid(dfs(cur), cur);
	root[cur] = 1;
	cnt[0] = 0;
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (!root[next]) {
			get_cnt(cost, false, next);
			get_cnt(cost, true, next);
		}
	}

	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (!root[next]) {
			del(cost, next);
		}
	}
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		if (!root[next]) {
			centroid(next);
		}
	}
}

void get_cnt(int sum, bool filling, int cur, int par = -1, int depth = 1) {
	if (sum > K) {
		return;
	}
	if (filling) {
		minimize(cnt[sum], depth);
	}
	else {
		if (cnt[K - sum] != -1) {
			minimize(ans, depth + cnt[K - sum]);
		}
	}
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (next != par && !root[next]) {
			get_cnt(sum + cost, filling, next, cur, depth + 1);
		}
	}
}

inline void minimize(int& a, int b) {
	if (a == -1 || a > b) {
		a = b;
	}
}


// Get the centroid within the subtree.
int get_centroid(int size, int cur, int par = -1) {
	for (auto &oPair : adj[cur]) {
		int next = oPair.first;
		if (next != par && !root[next] && 2 * subSize[next] > size) {
			return get_centroid(size, next, cur);
		}
	}
	return cur;
}

// Find subtree size under each node.
int dfs(int cur, int par = -1) {
	subSize[cur] = 1;
	for (auto &oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (next != par && !root[next]) {
			subSize[cur] += dfs(next, cur);
		}
	}
	return subSize[cur];
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:31:2: error: 'centroid' was not declared in this scope
   31 |  centroid();
      |  ^~~~~~~~
race.cpp: In function 'int centroid(int)':
race.cpp:49:21: error: 'dfs' was not declared in this scope; did you mean 'ffs'?
   49 |  cur = get_centroid(dfs(cur), cur);
      |                     ^~~
      |                     ffs
race.cpp:49:8: error: 'get_centroid' was not declared in this scope; did you mean 'centroid'?
   49 |  cur = get_centroid(dfs(cur), cur);
      |        ^~~~~~~~~~~~
      |        centroid
race.cpp:56:4: error: 'get_cnt' was not declared in this scope
   56 |    get_cnt(cost, false, next);
      |    ^~~~~~~
race.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
   74 | }
      | ^
race.cpp: In function 'void get_cnt(int, bool, int, int, int)':
race.cpp:81:3: error: 'minimize' was not declared in this scope
   81 |   minimize(cnt[sum], depth);
      |   ^~~~~~~~
race.cpp:85:4: error: 'minimize' was not declared in this scope
   85 |    minimize(ans, depth + cnt[K - sum]);
      |    ^~~~~~~~
race.cpp: In function 'int dfs(int, int)':
race.cpp:120:7: warning: unused variable 'cost' [-Wunused-variable]
  120 |   int cost = oPair.second;
      |       ^~~~