Submission #1032757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032757	2024-07-24T08:05:35 Z	vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

namespace mysol {

constexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;

constexpr int INF = 1e9;

// -----------------------------------------------------------------------------

int n, k;

struct edge {
	int v, w;
	edge() = default;
	edge(int v, int w): v(v), w(w) {}
};

vector<edge> g[N];

void add(int u, int v, int w) {
	g[u].emplace_back(v, w);
}

void Add(int u, int v, int w) {
	add(u, v, w), add(v, u, w);
}

int get_root(int);

// -----------------------------------------------------------------------------

int mp[M];

int vis[N], dis[N], dep[N];

int cnt, ans = INF;

void init(int u, int fa, int is, int ep) {
	if (is > k) return;
	++cnt;
	dis[cnt] = is, dep[cnt] = ep;
	for (auto t : g[u]) {
		if (t.v == fa || vis[t.v]) continue;
		init(t.v, u, is + t.w, ep + 1);
	}
}

void calc(int u) {
	mp[0] = cnt = 0;
	for (auto t : g[u]) {
		int v = t.v, w = t.w;
		if (vis[v]) continue;
		int st = cnt + 1;
		init(v, u, w, 1);
		for (int i = st; i <= cnt; ++i)
			ans = min(ans, mp[k - dis[i]] + dep[i]);
		for (int i = st; i <= cnt; ++i)
			mp[dis[i]] = min(mp[dis[i]], dep[i]);
	}
	for (int i = 1; i <= cnt; ++i) mp[dis[i]] = INF;
}

void solve(int u) {
	vis[u] = 1, calc(u);
	for (auto t : g[u]) {
		if (vis[t.v]) continue;
		solve(get_root(t.v));
	}
}

// -----------------------------------------------------------------------------

int siz[N], max_son[N];
int tot, root;

void dfs(int u, int fa) {
	siz[u] = 1, max_son[u] = 0;
	for (auto t : g[u]) {
		int v = t.v;
		if (v == fa || vis[v]) continue;
		dfs(v, u);
		siz[u] += siz[v];
		max_son[u] = max(max_son[u], siz[v]);
	}
	max_son[u] = max(max_son[u], tot - siz[u]);
	if (max_son[u] < max_son[root]) root = u;
}

int get_root(int u) {
	tot = siz[u], root = 0;
	return dfs(u, -1), root;
}

// -----------------------------------------------------------------------------

/*signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k;
	memset(mp, 0x3f, sizeof mp);
	for (int i = 1; i < n; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		Add(u + 1, v + 1, w);
	}
	max_son[0] = n + 1;
	siz[1] = n;
	solve(get_root(1));
	cout << (ans >= n ? -1 : ans) << endl;
	return 0;
}*/

}

using namespace mysol;

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	memset(mp, 0x3f, sizeof mp);
	for (int i = 0; i < n - 1; ++i) {
		int u = h[i][0], v = h[i][1], w = l[i];
		Add(u + 1, v + 1, w);
	}
	max_son[0] = n + 1;
	siz[1] = n;
	solve(get_root(1));
	return ans >= n ? -1 : ans;
}

Compilation message

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:128:11: error: 'h' was not declared in this scope
  128 |   int u = h[i][0], v = h[i][1], w = l[i];
      |           ^
race.cpp:129:14: error: 'v' was not declared in this scope
  129 |   Add(u + 1, v + 1, w);
      |              ^
race.cpp:129:21: error: 'w' was not declared in this scope
  129 |   Add(u + 1, v + 1, w);
      |                     ^