#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; }
const int MAXN = 2e5 + 5;
const int MAXK = 1e6 + 5;
const int INF = 1e9;
int n, k, avail[MAXN], sz[MAXN], exist[MAXK], cntE[MAXK];
vector <pair <int, int>> adj[MAXN];
long long ans;
int dfs_size(int u, int par) {
sz[u] = 1;
for (auto [v, _] : adj[u]) if(v != par and !avail[v]) {
sz[u] += dfs_size(v, u);
}
return sz[u];
}
int dfs_centroid(int u, int par, int n) {
for (auto [v, _] : adj[u]) if(v != par and !avail[v]) {
if(sz[v] > n / 2) return dfs_centroid(v, u, n);
}
return u;
}
int times;
int DFS(int u, int par, int cnt, int depth, int t, vector<pair<int, int>> &tmp) {
int ans = INF;
if(depth > k) return INF;
int wants = k - depth;
if(exist[wants] == t) minimize(ans, cnt + cntE[wants]);
tmp.emplace_back(depth, cnt);
for (auto [v, w] : adj[u]) if(v != par and !avail[v]) {
ans = min(ans, DFS(v, u, cnt + 1, depth + w, t, tmp));
}
return ans;
}
int solve(int u, int par) {
int n = dfs_size(u, par);
avail[u = dfs_centroid(u, par, n)] = true;
int ans = INF;
int t = ++times;
exist[0] = t, cntE[0] = 0;
for (auto [v, w] : adj[u]) if(v != par and !avail[v]) {
vector <pair <int, int>> tmp;
ans = min(ans, DFS(v, u, 1, w, t, tmp));
for (auto [d, c] : tmp) {
if(exist[d] != t || (exist[d] == t and cntE[d] > c)) {
exist[d] = t;
cntE[d] = c;
}
}
}
for (auto [v, _] : adj[u]) if(v != par and !avail[v]) {
ans = min(ans, solve(v, u));
}
return ans;
}
int best_path(int a, int b, int H[][2], int L[]) {
n = a, k = b;
REP(i, n - 1) {
adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
}
ans = solve(1, 0);
return (ans >= INF ? -1 : ans);
}
#ifdef LOCAL
#include "race.h"
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 500000
int N, K;
int H[MAX_N][2];
int L[MAX_N];
int solution;
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(2==scanf("%d %d",&N,&K));
for(i=0; i<N-1; i++)
my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
int ans;
read_input();
ans = best_path(N,K,H,L);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}
#endif
// Dream it. Wish it. Do it.
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5016 KB |
Output is correct |
3 |
Correct |
2 ms |
5020 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
5020 KB |
Output is correct |
9 |
Correct |
2 ms |
5020 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
3 ms |
4996 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5016 KB |
Output is correct |
3 |
Correct |
2 ms |
5020 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
5020 KB |
Output is correct |
9 |
Correct |
2 ms |
5020 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
3 ms |
4996 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5016 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
5076 KB |
Output is correct |
22 |
Correct |
5 ms |
10020 KB |
Output is correct |
23 |
Correct |
5 ms |
9300 KB |
Output is correct |
24 |
Correct |
5 ms |
10836 KB |
Output is correct |
25 |
Correct |
5 ms |
8616 KB |
Output is correct |
26 |
Correct |
4 ms |
7636 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
4 ms |
6612 KB |
Output is correct |
29 |
Correct |
4 ms |
7636 KB |
Output is correct |
30 |
Correct |
4 ms |
7892 KB |
Output is correct |
31 |
Correct |
5 ms |
8660 KB |
Output is correct |
32 |
Correct |
4 ms |
8788 KB |
Output is correct |
33 |
Correct |
6 ms |
10324 KB |
Output is correct |
34 |
Correct |
5 ms |
9556 KB |
Output is correct |
35 |
Correct |
7 ms |
10916 KB |
Output is correct |
36 |
Correct |
6 ms |
11476 KB |
Output is correct |
37 |
Correct |
4 ms |
8916 KB |
Output is correct |
38 |
Correct |
4 ms |
7380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5016 KB |
Output is correct |
3 |
Correct |
2 ms |
5020 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
5020 KB |
Output is correct |
9 |
Correct |
2 ms |
5020 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
3 ms |
4996 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5016 KB |
Output is correct |
19 |
Correct |
86 ms |
12080 KB |
Output is correct |
20 |
Correct |
82 ms |
11980 KB |
Output is correct |
21 |
Correct |
86 ms |
12236 KB |
Output is correct |
22 |
Correct |
81 ms |
12272 KB |
Output is correct |
23 |
Correct |
54 ms |
12228 KB |
Output is correct |
24 |
Correct |
40 ms |
12164 KB |
Output is correct |
25 |
Correct |
82 ms |
14788 KB |
Output is correct |
26 |
Correct |
65 ms |
18200 KB |
Output is correct |
27 |
Correct |
111 ms |
19328 KB |
Output is correct |
28 |
Correct |
160 ms |
30624 KB |
Output is correct |
29 |
Correct |
172 ms |
29876 KB |
Output is correct |
30 |
Correct |
107 ms |
19376 KB |
Output is correct |
31 |
Correct |
108 ms |
19272 KB |
Output is correct |
32 |
Correct |
139 ms |
19496 KB |
Output is correct |
33 |
Correct |
132 ms |
18236 KB |
Output is correct |
34 |
Correct |
112 ms |
19084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5016 KB |
Output is correct |
3 |
Correct |
2 ms |
5020 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
5020 KB |
Output is correct |
9 |
Correct |
2 ms |
5020 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
3 ms |
4996 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
5016 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
5076 KB |
Output is correct |
22 |
Correct |
5 ms |
10020 KB |
Output is correct |
23 |
Correct |
5 ms |
9300 KB |
Output is correct |
24 |
Correct |
5 ms |
10836 KB |
Output is correct |
25 |
Correct |
5 ms |
8616 KB |
Output is correct |
26 |
Correct |
4 ms |
7636 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
4 ms |
6612 KB |
Output is correct |
29 |
Correct |
4 ms |
7636 KB |
Output is correct |
30 |
Correct |
4 ms |
7892 KB |
Output is correct |
31 |
Correct |
5 ms |
8660 KB |
Output is correct |
32 |
Correct |
4 ms |
8788 KB |
Output is correct |
33 |
Correct |
6 ms |
10324 KB |
Output is correct |
34 |
Correct |
5 ms |
9556 KB |
Output is correct |
35 |
Correct |
7 ms |
10916 KB |
Output is correct |
36 |
Correct |
6 ms |
11476 KB |
Output is correct |
37 |
Correct |
4 ms |
8916 KB |
Output is correct |
38 |
Correct |
4 ms |
7380 KB |
Output is correct |
39 |
Correct |
86 ms |
12080 KB |
Output is correct |
40 |
Correct |
82 ms |
11980 KB |
Output is correct |
41 |
Correct |
86 ms |
12236 KB |
Output is correct |
42 |
Correct |
81 ms |
12272 KB |
Output is correct |
43 |
Correct |
54 ms |
12228 KB |
Output is correct |
44 |
Correct |
40 ms |
12164 KB |
Output is correct |
45 |
Correct |
82 ms |
14788 KB |
Output is correct |
46 |
Correct |
65 ms |
18200 KB |
Output is correct |
47 |
Correct |
111 ms |
19328 KB |
Output is correct |
48 |
Correct |
160 ms |
30624 KB |
Output is correct |
49 |
Correct |
172 ms |
29876 KB |
Output is correct |
50 |
Correct |
107 ms |
19376 KB |
Output is correct |
51 |
Correct |
108 ms |
19272 KB |
Output is correct |
52 |
Correct |
139 ms |
19496 KB |
Output is correct |
53 |
Correct |
132 ms |
18236 KB |
Output is correct |
54 |
Correct |
112 ms |
19084 KB |
Output is correct |
55 |
Correct |
8 ms |
5844 KB |
Output is correct |
56 |
Correct |
9 ms |
5832 KB |
Output is correct |
57 |
Correct |
55 ms |
12660 KB |
Output is correct |
58 |
Correct |
29 ms |
11844 KB |
Output is correct |
59 |
Correct |
71 ms |
19024 KB |
Output is correct |
60 |
Correct |
284 ms |
35680 KB |
Output is correct |
61 |
Correct |
129 ms |
19548 KB |
Output is correct |
62 |
Correct |
125 ms |
19540 KB |
Output is correct |
63 |
Correct |
169 ms |
19552 KB |
Output is correct |
64 |
Correct |
305 ms |
22872 KB |
Output is correct |
65 |
Correct |
156 ms |
20204 KB |
Output is correct |
66 |
Correct |
263 ms |
35668 KB |
Output is correct |
67 |
Correct |
81 ms |
20032 KB |
Output is correct |
68 |
Correct |
154 ms |
25448 KB |
Output is correct |
69 |
Correct |
196 ms |
25772 KB |
Output is correct |
70 |
Correct |
203 ms |
24712 KB |
Output is correct |