# include <bits/stdc++.h>
# include "race.h"
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
# define pll pair <ll, ll>
# define pii pair <int, int>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 2e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 998244353;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
using namespace std;
int n, k, ans;
vector <pii> g[maxn];
int sz[maxn];
bool used[maxn];
int mn[maxn * 5];
void dfs_calc (int v, int pa)
{
sz[v] = 1;
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (to == pa || used[to]) continue;
dfs_calc(to, v);
sz[v] += sz[to];
}
}
int find_c (int v, int pa, int siz)
{
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (to == pa || used[to]) continue;
if (sz[to] + sz[to] > siz)
{
return find_c(to, v, siz);
}
}
return v;
}
void dfs_add (int v, int pa, int d1, int d2)
{
if (d1 > k) return;
mn[d1] = min(mn[d1], d2);
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (to == pa || used[to]) continue;
dfs_add(to, v, d1 + w, d2 + 1);
}
}
void dfs_del (int v, int pa, ll d1, int d2)
{
if (d1 > k) return;
mn[d1] = inf;
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (to == pa || used[to]) continue;
dfs_del(to, v, d1 + w, d2 + 1);
}
}
void dfs_ans (int v, int pa, ll d1, int d2)
{
if (d1 > k) return;
ans = min(ans, d2 + mn[k - d1]);
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (to == pa || used[to]) continue;
dfs_ans(to, v, d1 + w, d2 + 1);
}
}
void centroid (int v)
{
dfs_calc(v, v);
v = find_c(v, v, sz[v]);
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (used[to]) continue;
dfs_ans(to, v, w, 1);
dfs_add(to, v, w, 1);
}
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (used[to]) continue;
dfs_del(to, v, w, 1);
}
used[v] = 1;
for (pii i : g[v])
{
int to = i.ff, w = i.ss;
if (used[to]) continue;
centroid(to);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N, k = K, ans = inf;
for(int i = 0; i < n - 1; ++i){
g[H[i][0] + 1].pb({H[i][1] + 1, L[i]});
g[H[i][1] + 1].pb({H[i][0] + 1, L[i]});
}
for (int i = 1; i <= k; ++i) mn[i] = inf;
centroid(1);
return (ans == inf ? -1 : ans);
}
Compilation message
race.cpp: In function 'void dfs_calc(int, int)':
race.cpp:36:18: warning: unused variable 'w' [-Wunused-variable]
36 | int to = i.ff, w = i.ss;
| ^
race.cpp: In function 'int find_c(int, int, int)':
race.cpp:47:18: warning: unused variable 'w' [-Wunused-variable]
47 | int to = i.ff, w = i.ss;
| ^
race.cpp: In function 'void centroid(int)':
race.cpp:113:18: warning: unused variable 'w' [-Wunused-variable]
113 | int to = i.ff, w = i.ss;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5016 KB |
Output is correct |
22 |
Correct |
5 ms |
8660 KB |
Output is correct |
23 |
Correct |
5 ms |
8020 KB |
Output is correct |
24 |
Correct |
5 ms |
8420 KB |
Output is correct |
25 |
Correct |
5 ms |
8276 KB |
Output is correct |
26 |
Correct |
4 ms |
6352 KB |
Output is correct |
27 |
Correct |
7 ms |
8148 KB |
Output is correct |
28 |
Correct |
3 ms |
5844 KB |
Output is correct |
29 |
Correct |
4 ms |
6356 KB |
Output is correct |
30 |
Correct |
4 ms |
6484 KB |
Output is correct |
31 |
Correct |
4 ms |
7636 KB |
Output is correct |
32 |
Correct |
4 ms |
7764 KB |
Output is correct |
33 |
Correct |
6 ms |
8020 KB |
Output is correct |
34 |
Correct |
4 ms |
7380 KB |
Output is correct |
35 |
Correct |
4 ms |
8276 KB |
Output is correct |
36 |
Correct |
5 ms |
8660 KB |
Output is correct |
37 |
Correct |
5 ms |
8148 KB |
Output is correct |
38 |
Correct |
4 ms |
6996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
136 ms |
10324 KB |
Output is correct |
20 |
Correct |
126 ms |
10228 KB |
Output is correct |
21 |
Correct |
127 ms |
10264 KB |
Output is correct |
22 |
Correct |
132 ms |
10412 KB |
Output is correct |
23 |
Correct |
78 ms |
10572 KB |
Output is correct |
24 |
Correct |
58 ms |
10380 KB |
Output is correct |
25 |
Correct |
147 ms |
13876 KB |
Output is correct |
26 |
Correct |
89 ms |
17616 KB |
Output is correct |
27 |
Correct |
142 ms |
15888 KB |
Output is correct |
28 |
Correct |
268 ms |
30284 KB |
Output is correct |
29 |
Correct |
223 ms |
28988 KB |
Output is correct |
30 |
Correct |
154 ms |
15884 KB |
Output is correct |
31 |
Correct |
171 ms |
15876 KB |
Output is correct |
32 |
Correct |
203 ms |
15820 KB |
Output is correct |
33 |
Correct |
193 ms |
14724 KB |
Output is correct |
34 |
Correct |
172 ms |
14668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5016 KB |
Output is correct |
22 |
Correct |
5 ms |
8660 KB |
Output is correct |
23 |
Correct |
5 ms |
8020 KB |
Output is correct |
24 |
Correct |
5 ms |
8420 KB |
Output is correct |
25 |
Correct |
5 ms |
8276 KB |
Output is correct |
26 |
Correct |
4 ms |
6352 KB |
Output is correct |
27 |
Correct |
7 ms |
8148 KB |
Output is correct |
28 |
Correct |
3 ms |
5844 KB |
Output is correct |
29 |
Correct |
4 ms |
6356 KB |
Output is correct |
30 |
Correct |
4 ms |
6484 KB |
Output is correct |
31 |
Correct |
4 ms |
7636 KB |
Output is correct |
32 |
Correct |
4 ms |
7764 KB |
Output is correct |
33 |
Correct |
6 ms |
8020 KB |
Output is correct |
34 |
Correct |
4 ms |
7380 KB |
Output is correct |
35 |
Correct |
4 ms |
8276 KB |
Output is correct |
36 |
Correct |
5 ms |
8660 KB |
Output is correct |
37 |
Correct |
5 ms |
8148 KB |
Output is correct |
38 |
Correct |
4 ms |
6996 KB |
Output is correct |
39 |
Correct |
136 ms |
10324 KB |
Output is correct |
40 |
Correct |
126 ms |
10228 KB |
Output is correct |
41 |
Correct |
127 ms |
10264 KB |
Output is correct |
42 |
Correct |
132 ms |
10412 KB |
Output is correct |
43 |
Correct |
78 ms |
10572 KB |
Output is correct |
44 |
Correct |
58 ms |
10380 KB |
Output is correct |
45 |
Correct |
147 ms |
13876 KB |
Output is correct |
46 |
Correct |
89 ms |
17616 KB |
Output is correct |
47 |
Correct |
142 ms |
15888 KB |
Output is correct |
48 |
Correct |
268 ms |
30284 KB |
Output is correct |
49 |
Correct |
223 ms |
28988 KB |
Output is correct |
50 |
Correct |
154 ms |
15884 KB |
Output is correct |
51 |
Correct |
171 ms |
15876 KB |
Output is correct |
52 |
Correct |
203 ms |
15820 KB |
Output is correct |
53 |
Correct |
193 ms |
14724 KB |
Output is correct |
54 |
Correct |
172 ms |
14668 KB |
Output is correct |
55 |
Correct |
12 ms |
5716 KB |
Output is correct |
56 |
Correct |
13 ms |
5660 KB |
Output is correct |
57 |
Correct |
74 ms |
11888 KB |
Output is correct |
58 |
Correct |
32 ms |
11648 KB |
Output is correct |
59 |
Correct |
89 ms |
19768 KB |
Output is correct |
60 |
Correct |
482 ms |
36288 KB |
Output is correct |
61 |
Correct |
182 ms |
18968 KB |
Output is correct |
62 |
Correct |
228 ms |
22764 KB |
Output is correct |
63 |
Correct |
261 ms |
22812 KB |
Output is correct |
64 |
Correct |
512 ms |
21160 KB |
Output is correct |
65 |
Correct |
221 ms |
19740 KB |
Output is correct |
66 |
Correct |
336 ms |
33612 KB |
Output is correct |
67 |
Correct |
104 ms |
23444 KB |
Output is correct |
68 |
Correct |
251 ms |
23416 KB |
Output is correct |
69 |
Correct |
295 ms |
23680 KB |
Output is correct |
70 |
Correct |
288 ms |
22944 KB |
Output is correct |