답안 #852455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852455	2023-09-21T20:12:31 Z	kawchar85	경주 (Race) (IOI11_race)	C++17	100 / 100	289 ms	37456 KB

race

/*
https://oj.uz/problem/view/IOI11_race

You are given a weight tree with N nodes, indexed from 1 to N.
Find the minimum number of edges used in a path with length K or
print “-1” if the path doesn’t exist.

1≤N≤2×10^5,1≤wi,j∈N≤10^6,1≤K≤10^6
*/

#include <bits/stdc++.h>
using namespace std;

#define MAX 200005
typedef long long ll;

vector<pair<int, int>> adj[MAX];
bool is_removed[MAX];
int n, k, ans, sz[MAX], cnt[1000006];

int get_size(int u, int p = -1) {
    sz[u] = 1;
    for(auto [v, w] : adj[u]) {
        if(v == p || is_removed[v]) continue;
        sz[u] += get_size(v, u);
    }
    return sz[u];
}

int get_centroid(int u, int n, int p = -1) {
    for(auto [v, w] : adj[u]) {
        if(v == p || is_removed[v]) continue;
        if(sz[v] * 2 > n) return get_centroid(v, n, u);
    }
    return u;
}

void get_cnts(int sum, int u, int p, bool f, int depth = 1) {
    if(sum > k) return;
    if(f) cnt[sum] = min(cnt[sum], depth);
    else ans = min(ans, depth + cnt[k - sum]);
    for(auto [v, w] : adj[u]) {
        if(v == p || is_removed[v]) continue;
        get_cnts(sum + w, v, u, f, depth + 1);
    }
}

void del(int sum, int u, int p = -1) {
    if(sum > k) return;
    cnt[sum] = 2e7;
    for(auto [v, w] : adj[u]) {
        if(v == p || is_removed[v]) continue;
        del(sum + w, v, u);
    }
}

void build_centroid_decomposition(int u = 0) {
    int c = get_centroid(u, get_size(u));

    cnt[0] = 0;
    for(auto [v, w] : adj[c]) {
        if(is_removed[v]) continue;
        get_cnts(w, v, c, 0);
        get_cnts(w, v, c, 1);
    }
    for(auto [v, w] : adj[c]) {
        if(is_removed[v]) continue;
        del(w, v, c);
    }

    is_removed[c] = 1;
    for(auto [v, w] : adj[c]) {
        if(is_removed[v]) continue;
        build_centroid_decomposition(v);
    }
}

int best_path(int N, int K, int h[][2], int l[]) {
    n = N;
    k = K;
    for(int i = 0; i < n; i++) {
        adj[i].clear();
        is_removed[i] = 0;
        sz[i] = 0;
    }
    for(int i = 0; i < 1000006; i++) {
        cnt[i] = 2e7;
    }
    for(int i = 0, u, v; i < n - 1; ++i) {
        u = h[i][0];
        v = h[i][1];
        adj[u].push_back(make_pair(v, l[i]));
        adj[v].push_back(make_pair(u, l[i]));
    }
    ans = 2e7;
    build_centroid_decomposition();
    if(ans > 1e7) ans = -1;
    return ans;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13656 KB	Output is correct
2	Correct	3 ms	13656 KB	Output is correct
3	Correct	3 ms	13656 KB	Output is correct
4	Correct	3 ms	13660 KB	Output is correct
5	Correct	3 ms	13656 KB	Output is correct
6	Correct	3 ms	13660 KB	Output is correct
7	Correct	3 ms	13656 KB	Output is correct
8	Correct	3 ms	13660 KB	Output is correct
9	Correct	3 ms	13656 KB	Output is correct
10	Correct	3 ms	13656 KB	Output is correct
11	Correct	3 ms	13912 KB	Output is correct
12	Correct	3 ms	13660 KB	Output is correct
13	Correct	3 ms	13656 KB	Output is correct
14	Correct	3 ms	13656 KB	Output is correct
15	Correct	3 ms	13660 KB	Output is correct
16	Correct	3 ms	13660 KB	Output is correct
17	Correct	3 ms	13656 KB	Output is correct
18	Correct	3 ms	13656 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13656 KB	Output is correct
2	Correct	3 ms	13656 KB	Output is correct
3	Correct	3 ms	13656 KB	Output is correct
4	Correct	3 ms	13660 KB	Output is correct
5	Correct	3 ms	13656 KB	Output is correct
6	Correct	3 ms	13660 KB	Output is correct
7	Correct	3 ms	13656 KB	Output is correct
8	Correct	3 ms	13660 KB	Output is correct
9	Correct	3 ms	13656 KB	Output is correct
10	Correct	3 ms	13656 KB	Output is correct
11	Correct	3 ms	13912 KB	Output is correct
12	Correct	3 ms	13660 KB	Output is correct
13	Correct	3 ms	13656 KB	Output is correct
14	Correct	3 ms	13656 KB	Output is correct
15	Correct	3 ms	13660 KB	Output is correct
16	Correct	3 ms	13660 KB	Output is correct
17	Correct	3 ms	13656 KB	Output is correct
18	Correct	3 ms	13656 KB	Output is correct
19	Correct	4 ms	13652 KB	Output is correct
20	Correct	3 ms	13656 KB	Output is correct
21	Correct	3 ms	13656 KB	Output is correct
22	Correct	3 ms	13660 KB	Output is correct
23	Correct	3 ms	13656 KB	Output is correct
24	Correct	3 ms	13660 KB	Output is correct
25	Correct	3 ms	13656 KB	Output is correct
26	Correct	3 ms	13656 KB	Output is correct
27	Correct	3 ms	13912 KB	Output is correct
28	Correct	3 ms	13660 KB	Output is correct
29	Correct	4 ms	13656 KB	Output is correct
30	Correct	3 ms	13656 KB	Output is correct
31	Correct	3 ms	13656 KB	Output is correct
32	Correct	3 ms	13860 KB	Output is correct
33	Correct	3 ms	13656 KB	Output is correct
34	Correct	3 ms	13656 KB	Output is correct
35	Correct	3 ms	13656 KB	Output is correct
36	Correct	3 ms	13656 KB	Output is correct
37	Correct	3 ms	13660 KB	Output is correct
38	Correct	3 ms	13660 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13656 KB	Output is correct
2	Correct	3 ms	13656 KB	Output is correct
3	Correct	3 ms	13656 KB	Output is correct
4	Correct	3 ms	13660 KB	Output is correct
5	Correct	3 ms	13656 KB	Output is correct
6	Correct	3 ms	13660 KB	Output is correct
7	Correct	3 ms	13656 KB	Output is correct
8	Correct	3 ms	13660 KB	Output is correct
9	Correct	3 ms	13656 KB	Output is correct
10	Correct	3 ms	13656 KB	Output is correct
11	Correct	3 ms	13912 KB	Output is correct
12	Correct	3 ms	13660 KB	Output is correct
13	Correct	3 ms	13656 KB	Output is correct
14	Correct	3 ms	13656 KB	Output is correct
15	Correct	3 ms	13660 KB	Output is correct
16	Correct	3 ms	13660 KB	Output is correct
17	Correct	3 ms	13656 KB	Output is correct
18	Correct	3 ms	13656 KB	Output is correct
19	Correct	84 ms	20816 KB	Output is correct
20	Correct	95 ms	20712 KB	Output is correct
21	Correct	100 ms	20816 KB	Output is correct
22	Correct	80 ms	20816 KB	Output is correct
23	Correct	48 ms	21208 KB	Output is correct
24	Correct	38 ms	21092 KB	Output is correct
25	Correct	79 ms	23896 KB	Output is correct
26	Correct	81 ms	26708 KB	Output is correct
27	Correct	102 ms	26460 KB	Output is correct
28	Correct	142 ms	37456 KB	Output is correct
29	Correct	147 ms	36616 KB	Output is correct
30	Correct	106 ms	26216 KB	Output is correct
31	Correct	101 ms	26192 KB	Output is correct
32	Correct	115 ms	26452 KB	Output is correct
33	Correct	126 ms	25168 KB	Output is correct
34	Correct	108 ms	26296 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13656 KB	Output is correct
2	Correct	3 ms	13656 KB	Output is correct
3	Correct	3 ms	13656 KB	Output is correct
4	Correct	3 ms	13660 KB	Output is correct
5	Correct	3 ms	13656 KB	Output is correct
6	Correct	3 ms	13660 KB	Output is correct
7	Correct	3 ms	13656 KB	Output is correct
8	Correct	3 ms	13660 KB	Output is correct
9	Correct	3 ms	13656 KB	Output is correct
10	Correct	3 ms	13656 KB	Output is correct
11	Correct	3 ms	13912 KB	Output is correct
12	Correct	3 ms	13660 KB	Output is correct
13	Correct	3 ms	13656 KB	Output is correct
14	Correct	3 ms	13656 KB	Output is correct
15	Correct	3 ms	13660 KB	Output is correct
16	Correct	3 ms	13660 KB	Output is correct
17	Correct	3 ms	13656 KB	Output is correct
18	Correct	3 ms	13656 KB	Output is correct
19	Correct	4 ms	13652 KB	Output is correct
20	Correct	3 ms	13656 KB	Output is correct
21	Correct	3 ms	13656 KB	Output is correct
22	Correct	3 ms	13660 KB	Output is correct
23	Correct	3 ms	13656 KB	Output is correct
24	Correct	3 ms	13660 KB	Output is correct
25	Correct	3 ms	13656 KB	Output is correct
26	Correct	3 ms	13656 KB	Output is correct
27	Correct	3 ms	13912 KB	Output is correct
28	Correct	3 ms	13660 KB	Output is correct
29	Correct	4 ms	13656 KB	Output is correct
30	Correct	3 ms	13656 KB	Output is correct
31	Correct	3 ms	13656 KB	Output is correct
32	Correct	3 ms	13860 KB	Output is correct
33	Correct	3 ms	13656 KB	Output is correct
34	Correct	3 ms	13656 KB	Output is correct
35	Correct	3 ms	13656 KB	Output is correct
36	Correct	3 ms	13656 KB	Output is correct
37	Correct	3 ms	13660 KB	Output is correct
38	Correct	3 ms	13660 KB	Output is correct
39	Correct	84 ms	20816 KB	Output is correct
40	Correct	95 ms	20712 KB	Output is correct
41	Correct	100 ms	20816 KB	Output is correct
42	Correct	80 ms	20816 KB	Output is correct
43	Correct	48 ms	21208 KB	Output is correct
44	Correct	38 ms	21092 KB	Output is correct
45	Correct	79 ms	23896 KB	Output is correct
46	Correct	81 ms	26708 KB	Output is correct
47	Correct	102 ms	26460 KB	Output is correct
48	Correct	142 ms	37456 KB	Output is correct
49	Correct	147 ms	36616 KB	Output is correct
50	Correct	106 ms	26216 KB	Output is correct
51	Correct	101 ms	26192 KB	Output is correct
52	Correct	115 ms	26452 KB	Output is correct
53	Correct	126 ms	25168 KB	Output is correct
54	Correct	108 ms	26296 KB	Output is correct
55	Correct	9 ms	14168 KB	Output is correct
56	Correct	9 ms	14168 KB	Output is correct
57	Correct	60 ms	21012 KB	Output is correct
58	Correct	28 ms	20676 KB	Output is correct
59	Correct	77 ms	26608 KB	Output is correct
60	Correct	289 ms	36944 KB	Output is correct
61	Correct	112 ms	26448 KB	Output is correct
62	Correct	126 ms	26192 KB	Output is correct
63	Correct	141 ms	26216 KB	Output is correct
64	Correct	253 ms	26452 KB	Output is correct
65	Correct	120 ms	27216 KB	Output is correct
66	Correct	219 ms	34640 KB	Output is correct
67	Correct	72 ms	26836 KB	Output is correct
68	Correct	135 ms	27008 KB	Output is correct
69	Correct	139 ms	27216 KB	Output is correct
70	Correct	143 ms	26704 KB	Output is correct

답안 #852455

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 22.0 / 22.0

Subtask #4 57.0 / 57.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
22.0 / 22.0

Subtask #4
57.0 / 57.0