#include <bits/stdc++.h>
#include "race.h"
#define va first //정점
#define vb second //비용
using namespace std;
typedef pair<int,int> pii;
const int mxn = 200005, mxk = 1e6 + 5, inf = 1e9;
vector<pii> G[mxn];
int clk_dfs, clk_dnc;
int cnt[mxn], vis[mxn], par[mxn];
int del[mxn];
int dep[mxn];
int min_cnt[mxk], min_cnt_chk[mxk];
pii Q[mxn];
int q_f, q_r;
int N, K;
int ans = inf;
void dfsi(int v){
cnt[v] = 1;
vis[v] = clk_dfs;
for(pii &p : G[v]){
if(del[p.va] || vis[p.va] == clk_dfs) continue;
dfsi(p.va);
par[p.va] = v;
cnt[v] += cnt[p.va];
}
}
int get_cen(int v, int sz){
for(pii &p : G[v]){
if(del[p.va] || p.va == par[v]) continue;
if(cnt[p.va] > sz/2) return get_cen(p.va, sz);
}
return v;
}
void dfs_race(int v, int sum){
vis[v] = clk_dfs;
Q[q_r++] = {sum, dep[v]}; //va = cost, vb = dep;
for(pii &p : G[v]){
if(del[p.va] || vis[p.va] == clk_dfs) continue;
par[p.va] = v;
dep[p.va] = dep[v] + 1;
dfs_race(p.va, sum + p.vb);
}
}
void dnc(int root){
pii tmp;
++clk_dfs;
dfsi(root);
int cen = get_cen(root, cnt[root]);
min_cnt[0] = 0; min_cnt_chk[0] = ++clk_dnc; //centroid itself!
for(pii &p : G[cen]){
if(del[p.va]) continue;
q_f = q_r = 0;
dep[p.va] = 1;
vis[cen] = ++clk_dfs;
dfs_race(p.va, p.vb);
for(int i = q_f; i < q_r; i++){
if(Q[i].va > K) continue;
if(min_cnt_chk[K - Q[i].va] == clk_dnc){
ans = min(ans, Q[i].vb + min_cnt[K - Q[i].va]);
}
}
while(q_f != q_r){
tmp = Q[q_f++];
if(tmp.va > K) continue;
if(min_cnt_chk[tmp.va] != clk_dnc || min_cnt[tmp.va] > tmp.vb){
min_cnt_chk[tmp.va] = clk_dnc;
min_cnt[tmp.va] = tmp.vb;
}
}
}
del[cen] = 1;
for(pii &p : G[cen]){
if(del[p.va]) continue;
dnc(p.va);
}
}
int best_path(int n, int k, int H[][2], int L[]){
N = n;
K = k;
for(int i = 0; i < n-1; i++){
G[H[i][0]].emplace_back(H[i][1], L[i]);
G[H[i][1]].emplace_back(H[i][0], L[i]);
}
dnc(1);
return ans == inf ? -1 : ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5188 KB |
Output is correct |
3 |
Correct |
5 ms |
5256 KB |
Output is correct |
4 |
Correct |
5 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
5 ms |
5256 KB |
Output is correct |
7 |
Correct |
5 ms |
5408 KB |
Output is correct |
8 |
Correct |
5 ms |
5408 KB |
Output is correct |
9 |
Correct |
6 ms |
5408 KB |
Output is correct |
10 |
Correct |
6 ms |
5408 KB |
Output is correct |
11 |
Correct |
5 ms |
5408 KB |
Output is correct |
12 |
Correct |
6 ms |
5432 KB |
Output is correct |
13 |
Correct |
6 ms |
5436 KB |
Output is correct |
14 |
Correct |
6 ms |
5436 KB |
Output is correct |
15 |
Correct |
6 ms |
5436 KB |
Output is correct |
16 |
Correct |
6 ms |
5436 KB |
Output is correct |
17 |
Correct |
6 ms |
5436 KB |
Output is correct |
18 |
Correct |
6 ms |
5436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5188 KB |
Output is correct |
3 |
Correct |
5 ms |
5256 KB |
Output is correct |
4 |
Correct |
5 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
5 ms |
5256 KB |
Output is correct |
7 |
Correct |
5 ms |
5408 KB |
Output is correct |
8 |
Correct |
5 ms |
5408 KB |
Output is correct |
9 |
Correct |
6 ms |
5408 KB |
Output is correct |
10 |
Correct |
6 ms |
5408 KB |
Output is correct |
11 |
Correct |
5 ms |
5408 KB |
Output is correct |
12 |
Correct |
6 ms |
5432 KB |
Output is correct |
13 |
Correct |
6 ms |
5436 KB |
Output is correct |
14 |
Correct |
6 ms |
5436 KB |
Output is correct |
15 |
Correct |
6 ms |
5436 KB |
Output is correct |
16 |
Correct |
6 ms |
5436 KB |
Output is correct |
17 |
Correct |
6 ms |
5436 KB |
Output is correct |
18 |
Correct |
6 ms |
5436 KB |
Output is correct |
19 |
Correct |
5 ms |
5436 KB |
Output is correct |
20 |
Correct |
6 ms |
5436 KB |
Output is correct |
21 |
Correct |
6 ms |
5436 KB |
Output is correct |
22 |
Correct |
11 ms |
10364 KB |
Output is correct |
23 |
Correct |
13 ms |
10364 KB |
Output is correct |
24 |
Correct |
12 ms |
11132 KB |
Output is correct |
25 |
Correct |
10 ms |
11132 KB |
Output is correct |
26 |
Correct |
9 ms |
11132 KB |
Output is correct |
27 |
Correct |
8 ms |
11132 KB |
Output is correct |
28 |
Correct |
9 ms |
11132 KB |
Output is correct |
29 |
Correct |
10 ms |
11132 KB |
Output is correct |
30 |
Correct |
10 ms |
11132 KB |
Output is correct |
31 |
Correct |
10 ms |
11132 KB |
Output is correct |
32 |
Correct |
10 ms |
11132 KB |
Output is correct |
33 |
Correct |
13 ms |
11132 KB |
Output is correct |
34 |
Correct |
13 ms |
11132 KB |
Output is correct |
35 |
Correct |
12 ms |
11612 KB |
Output is correct |
36 |
Correct |
14 ms |
12252 KB |
Output is correct |
37 |
Correct |
12 ms |
12252 KB |
Output is correct |
38 |
Correct |
11 ms |
12252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5188 KB |
Output is correct |
3 |
Correct |
5 ms |
5256 KB |
Output is correct |
4 |
Correct |
5 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
5 ms |
5256 KB |
Output is correct |
7 |
Correct |
5 ms |
5408 KB |
Output is correct |
8 |
Correct |
5 ms |
5408 KB |
Output is correct |
9 |
Correct |
6 ms |
5408 KB |
Output is correct |
10 |
Correct |
6 ms |
5408 KB |
Output is correct |
11 |
Correct |
5 ms |
5408 KB |
Output is correct |
12 |
Correct |
6 ms |
5432 KB |
Output is correct |
13 |
Correct |
6 ms |
5436 KB |
Output is correct |
14 |
Correct |
6 ms |
5436 KB |
Output is correct |
15 |
Correct |
6 ms |
5436 KB |
Output is correct |
16 |
Correct |
6 ms |
5436 KB |
Output is correct |
17 |
Correct |
6 ms |
5436 KB |
Output is correct |
18 |
Correct |
6 ms |
5436 KB |
Output is correct |
19 |
Correct |
270 ms |
12412 KB |
Output is correct |
20 |
Correct |
253 ms |
12540 KB |
Output is correct |
21 |
Correct |
190 ms |
12540 KB |
Output is correct |
22 |
Correct |
185 ms |
12540 KB |
Output is correct |
23 |
Correct |
198 ms |
12668 KB |
Output is correct |
24 |
Correct |
133 ms |
12668 KB |
Output is correct |
25 |
Correct |
394 ms |
16440 KB |
Output is correct |
26 |
Correct |
138 ms |
16892 KB |
Output is correct |
27 |
Correct |
333 ms |
20728 KB |
Output is correct |
28 |
Correct |
940 ms |
27468 KB |
Output is correct |
29 |
Correct |
759 ms |
27468 KB |
Output is correct |
30 |
Correct |
244 ms |
27468 KB |
Output is correct |
31 |
Correct |
273 ms |
27468 KB |
Output is correct |
32 |
Correct |
363 ms |
27468 KB |
Output is correct |
33 |
Correct |
616 ms |
27468 KB |
Output is correct |
34 |
Correct |
553 ms |
27468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5188 KB |
Output is correct |
3 |
Correct |
5 ms |
5256 KB |
Output is correct |
4 |
Correct |
5 ms |
5256 KB |
Output is correct |
5 |
Correct |
7 ms |
5256 KB |
Output is correct |
6 |
Correct |
5 ms |
5256 KB |
Output is correct |
7 |
Correct |
5 ms |
5408 KB |
Output is correct |
8 |
Correct |
5 ms |
5408 KB |
Output is correct |
9 |
Correct |
6 ms |
5408 KB |
Output is correct |
10 |
Correct |
6 ms |
5408 KB |
Output is correct |
11 |
Correct |
5 ms |
5408 KB |
Output is correct |
12 |
Correct |
6 ms |
5432 KB |
Output is correct |
13 |
Correct |
6 ms |
5436 KB |
Output is correct |
14 |
Correct |
6 ms |
5436 KB |
Output is correct |
15 |
Correct |
6 ms |
5436 KB |
Output is correct |
16 |
Correct |
6 ms |
5436 KB |
Output is correct |
17 |
Correct |
6 ms |
5436 KB |
Output is correct |
18 |
Correct |
6 ms |
5436 KB |
Output is correct |
19 |
Correct |
5 ms |
5436 KB |
Output is correct |
20 |
Correct |
6 ms |
5436 KB |
Output is correct |
21 |
Correct |
6 ms |
5436 KB |
Output is correct |
22 |
Correct |
11 ms |
10364 KB |
Output is correct |
23 |
Correct |
13 ms |
10364 KB |
Output is correct |
24 |
Correct |
12 ms |
11132 KB |
Output is correct |
25 |
Correct |
10 ms |
11132 KB |
Output is correct |
26 |
Correct |
9 ms |
11132 KB |
Output is correct |
27 |
Correct |
8 ms |
11132 KB |
Output is correct |
28 |
Correct |
9 ms |
11132 KB |
Output is correct |
29 |
Correct |
10 ms |
11132 KB |
Output is correct |
30 |
Correct |
10 ms |
11132 KB |
Output is correct |
31 |
Correct |
10 ms |
11132 KB |
Output is correct |
32 |
Correct |
10 ms |
11132 KB |
Output is correct |
33 |
Correct |
13 ms |
11132 KB |
Output is correct |
34 |
Correct |
13 ms |
11132 KB |
Output is correct |
35 |
Correct |
12 ms |
11612 KB |
Output is correct |
36 |
Correct |
14 ms |
12252 KB |
Output is correct |
37 |
Correct |
12 ms |
12252 KB |
Output is correct |
38 |
Correct |
11 ms |
12252 KB |
Output is correct |
39 |
Correct |
270 ms |
12412 KB |
Output is correct |
40 |
Correct |
253 ms |
12540 KB |
Output is correct |
41 |
Correct |
190 ms |
12540 KB |
Output is correct |
42 |
Correct |
185 ms |
12540 KB |
Output is correct |
43 |
Correct |
198 ms |
12668 KB |
Output is correct |
44 |
Correct |
133 ms |
12668 KB |
Output is correct |
45 |
Correct |
394 ms |
16440 KB |
Output is correct |
46 |
Correct |
138 ms |
16892 KB |
Output is correct |
47 |
Correct |
333 ms |
20728 KB |
Output is correct |
48 |
Correct |
940 ms |
27468 KB |
Output is correct |
49 |
Correct |
759 ms |
27468 KB |
Output is correct |
50 |
Correct |
244 ms |
27468 KB |
Output is correct |
51 |
Correct |
273 ms |
27468 KB |
Output is correct |
52 |
Correct |
363 ms |
27468 KB |
Output is correct |
53 |
Correct |
616 ms |
27468 KB |
Output is correct |
54 |
Correct |
553 ms |
27468 KB |
Output is correct |
55 |
Correct |
15 ms |
27468 KB |
Output is correct |
56 |
Correct |
27 ms |
27468 KB |
Output is correct |
57 |
Correct |
99 ms |
27468 KB |
Output is correct |
58 |
Correct |
57 ms |
27468 KB |
Output is correct |
59 |
Correct |
139 ms |
27468 KB |
Output is correct |
60 |
Correct |
990 ms |
28448 KB |
Output is correct |
61 |
Correct |
307 ms |
28448 KB |
Output is correct |
62 |
Correct |
346 ms |
28448 KB |
Output is correct |
63 |
Correct |
360 ms |
28448 KB |
Output is correct |
64 |
Correct |
761 ms |
28448 KB |
Output is correct |
65 |
Correct |
544 ms |
28448 KB |
Output is correct |
66 |
Correct |
1203 ms |
34696 KB |
Output is correct |
67 |
Correct |
175 ms |
34696 KB |
Output is correct |
68 |
Correct |
501 ms |
34696 KB |
Output is correct |
69 |
Correct |
485 ms |
34696 KB |
Output is correct |
70 |
Correct |
488 ms |
34696 KB |
Output is correct |