| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1032756 |
2024-07-24T08:05:06 Z |
vjudge1 |
Race (IOI11_race) |
C++17 |
|
0 ms |
0 KB |
#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
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;
| ^~~
