Submission #1032756

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

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;
}*/

}

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 (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:123:2: error: 'n' was not declared in this scope; did you mean 'mysol::n'?
  123 |  n = N, k = K;
      |  ^
      |  mysol::n
race.cpp:16:5: note: 'mysol::n' declared here
   16 | int n, k;
      |     ^
race.cpp:123:9: error: 'k' was not declared in this scope; did you mean 'mysol::k'?
  123 |  n = N, k = K;
      |         ^
      |         mysol::k
race.cpp:16:8: note: 'mysol::k' declared here
   16 | int n, k;
      |        ^
race.cpp:124:9: error: 'mp' was not declared in this scope; did you mean 'mysol::mp'?
  124 |  memset(mp, 0x3f, sizeof mp);
      |         ^~
      |         mysol::mp
race.cpp:38:5: note: 'mysol::mp' declared here
   38 | int mp[M];
      |     ^~
race.cpp:126:11: error: 'h' was not declared in this scope
  126 |   int u = h[i][0], v = h[i][1], w = l[i];
      |           ^
race.cpp:127:14: error: 'v' was not declared in this scope
  127 |   Add(u + 1, v + 1, w);
      |              ^
race.cpp:127:21: error: 'w' was not declared in this scope
  127 |   Add(u + 1, v + 1, w);
      |                     ^
race.cpp:127:3: error: 'Add' was not declared in this scope; did you mean 'mysol::Add'?
  127 |   Add(u + 1, v + 1, w);
      |   ^~~
      |   mysol::Add
race.cpp:30:6: note: 'mysol::Add' declared here
   30 | void Add(int u, int v, int w) {
      |      ^~~
race.cpp:129:2: error: 'max_son' was not declared in this scope; did you mean 'mysol::max_son'?
  129 |  max_son[0] = n + 1;
      |  ^~~~~~~
      |  mysol::max_son
race.cpp:79:13: note: 'mysol::max_son' declared here
   79 | int siz[N], max_son[N];
      |             ^~~~~~~
race.cpp:130:2: error: 'siz' was not declared in this scope; did you mean 'mysol::siz'?
  130 |  siz[1] = n;
      |  ^~~
      |  mysol::siz
race.cpp:79:5: note: 'mysol::siz' declared here
   79 | int siz[N], max_son[N];
      |     ^~~
race.cpp:131:8: error: 'get_root' was not declared in this scope; did you mean 'mysol::get_root'?
  131 |  solve(get_root(1));
      |        ^~~~~~~~
      |        mysol::get_root
race.cpp:95:5: note: 'mysol::get_root' declared here
   95 | int get_root(int u) {
      |     ^~~~~~~~
race.cpp:131:2: error: 'solve' was not declared in this scope; did you mean 'mysol::solve'?
  131 |  solve(get_root(1));
      |  ^~~~~
      |  mysol::solve
race.cpp:69:6: note: 'mysol::solve' declared here
   69 | void solve(int u) {
      |      ^~~~~
race.cpp:132:9: error: 'ans' was not declared in this scope; did you mean 'mysol::ans'?
  132 |  return ans >= n ? -1 : ans;
      |         ^~~
      |         mysol::ans
race.cpp:42:10: note: 'mysol::ans' declared here
   42 | int cnt, ans = INF;
      |          ^~~