답안 #446435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446435	2021-07-21T22:33:39 Z	SirCovidThe19th	경주 (Race) (IOI11_race)	C++14	100 / 100	514 ms	87956 KB

race

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

#define f first
#define s second

int K, ans = INT_MAX; vector<pair<int, int>> adj[200005]; set<pair<int, int>> S[200005];

void dfs(int i, int p, int dis, int dep){
    S[i].insert({dis, dep});
    for (auto nxt : adj[i]) if (nxt.f != p){
        dfs(nxt.f, i, dis+nxt.s, dep+1);
        if (S[i].size() < S[nxt.f].size()) swap(S[i], S[nxt.f]);
        for (auto d : S[nxt.f]){
            int other = K+2*dis-d.f; auto x = S[i].lower_bound({other, -1});
            if (x != S[i].end() and (*x).f == other) ans = min(ans, d.s+(*x).s-2*dep);
        }for (auto d : S[nxt.f]) S[i].insert(d);
    }
}
int best_path(int n, int k, int h[][2], int l[]){
    for (int i = 0; i < n-1; i++){
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }K = k; dfs(0, 0, 0, 0); return (ans == INT_MAX) ? -1 : ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14412 KB	Output is correct
3	Correct	8 ms	14388 KB	Output is correct
4	Correct	8 ms	14412 KB	Output is correct
5	Correct	8 ms	14412 KB	Output is correct
6	Correct	10 ms	14396 KB	Output is correct
7	Correct	9 ms	14392 KB	Output is correct
8	Correct	9 ms	14412 KB	Output is correct
9	Correct	9 ms	14412 KB	Output is correct
10	Correct	9 ms	14412 KB	Output is correct
11	Correct	9 ms	14412 KB	Output is correct
12	Correct	8 ms	14412 KB	Output is correct
13	Correct	9 ms	14412 KB	Output is correct
14	Correct	8 ms	14404 KB	Output is correct
15	Correct	9 ms	14332 KB	Output is correct
16	Correct	8 ms	14412 KB	Output is correct
17	Correct	9 ms	14412 KB	Output is correct
18	Correct	10 ms	14412 KB	Output is correct
19	Correct	9 ms	14404 KB	Output is correct
20	Correct	10 ms	14412 KB	Output is correct
21	Correct	11 ms	14556 KB	Output is correct
22	Correct	10 ms	14656 KB	Output is correct
23	Correct	11 ms	14540 KB	Output is correct
24	Correct	10 ms	14540 KB	Output is correct
25	Correct	9 ms	14528 KB	Output is correct
26	Correct	10 ms	14540 KB	Output is correct
27	Correct	9 ms	14528 KB	Output is correct
28	Correct	10 ms	14540 KB	Output is correct
29	Correct	11 ms	14532 KB	Output is correct
30	Correct	11 ms	14536 KB	Output is correct
31	Correct	11 ms	14528 KB	Output is correct
32	Correct	10 ms	14540 KB	Output is correct
33	Correct	9 ms	14668 KB	Output is correct
34	Correct	9 ms	14540 KB	Output is correct
35	Correct	9 ms	14508 KB	Output is correct
36	Correct	9 ms	14540 KB	Output is correct
37	Correct	9 ms	14540 KB	Output is correct
38	Correct	9 ms	14568 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14412 KB	Output is correct
3	Correct	8 ms	14388 KB	Output is correct
4	Correct	8 ms	14412 KB	Output is correct
5	Correct	8 ms	14412 KB	Output is correct
6	Correct	10 ms	14396 KB	Output is correct
7	Correct	9 ms	14392 KB	Output is correct
8	Correct	9 ms	14412 KB	Output is correct
9	Correct	9 ms	14412 KB	Output is correct
10	Correct	9 ms	14412 KB	Output is correct
11	Correct	9 ms	14412 KB	Output is correct
12	Correct	8 ms	14412 KB	Output is correct
13	Correct	9 ms	14412 KB	Output is correct
14	Correct	8 ms	14404 KB	Output is correct
15	Correct	9 ms	14332 KB	Output is correct
16	Correct	8 ms	14412 KB	Output is correct
17	Correct	9 ms	14412 KB	Output is correct
18	Correct	10 ms	14412 KB	Output is correct
19	Correct	152 ms	35848 KB	Output is correct
20	Correct	160 ms	35852 KB	Output is correct
21	Correct	155 ms	35348 KB	Output is correct
22	Correct	161 ms	34268 KB	Output is correct
23	Correct	192 ms	45200 KB	Output is correct
24	Correct	146 ms	35196 KB	Output is correct
25	Correct	137 ms	39052 KB	Output is correct
26	Correct	88 ms	43520 KB	Output is correct
27	Correct	235 ms	43816 KB	Output is correct
28	Correct	350 ms	72884 KB	Output is correct
29	Correct	285 ms	71584 KB	Output is correct
30	Correct	288 ms	43848 KB	Output is correct
31	Correct	241 ms	43992 KB	Output is correct
32	Correct	361 ms	43892 KB	Output is correct
33	Correct	247 ms	44812 KB	Output is correct
34	Correct	359 ms	69812 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14412 KB	Output is correct
3	Correct	8 ms	14388 KB	Output is correct
4	Correct	8 ms	14412 KB	Output is correct
5	Correct	8 ms	14412 KB	Output is correct
6	Correct	10 ms	14396 KB	Output is correct
7	Correct	9 ms	14392 KB	Output is correct
8	Correct	9 ms	14412 KB	Output is correct
9	Correct	9 ms	14412 KB	Output is correct
10	Correct	9 ms	14412 KB	Output is correct
11	Correct	9 ms	14412 KB	Output is correct
12	Correct	8 ms	14412 KB	Output is correct
13	Correct	9 ms	14412 KB	Output is correct
14	Correct	8 ms	14404 KB	Output is correct
15	Correct	9 ms	14332 KB	Output is correct
16	Correct	8 ms	14412 KB	Output is correct
17	Correct	9 ms	14412 KB	Output is correct
18	Correct	10 ms	14412 KB	Output is correct
19	Correct	9 ms	14404 KB	Output is correct
20	Correct	10 ms	14412 KB	Output is correct
21	Correct	11 ms	14556 KB	Output is correct
22	Correct	10 ms	14656 KB	Output is correct
23	Correct	11 ms	14540 KB	Output is correct
24	Correct	10 ms	14540 KB	Output is correct
25	Correct	9 ms	14528 KB	Output is correct
26	Correct	10 ms	14540 KB	Output is correct
27	Correct	9 ms	14528 KB	Output is correct
28	Correct	10 ms	14540 KB	Output is correct
29	Correct	11 ms	14532 KB	Output is correct
30	Correct	11 ms	14536 KB	Output is correct
31	Correct	11 ms	14528 KB	Output is correct
32	Correct	10 ms	14540 KB	Output is correct
33	Correct	9 ms	14668 KB	Output is correct
34	Correct	9 ms	14540 KB	Output is correct
35	Correct	9 ms	14508 KB	Output is correct
36	Correct	9 ms	14540 KB	Output is correct
37	Correct	9 ms	14540 KB	Output is correct
38	Correct	9 ms	14568 KB	Output is correct
39	Correct	152 ms	35848 KB	Output is correct
40	Correct	160 ms	35852 KB	Output is correct
41	Correct	155 ms	35348 KB	Output is correct
42	Correct	161 ms	34268 KB	Output is correct
43	Correct	192 ms	45200 KB	Output is correct
44	Correct	146 ms	35196 KB	Output is correct
45	Correct	137 ms	39052 KB	Output is correct
46	Correct	88 ms	43520 KB	Output is correct
47	Correct	235 ms	43816 KB	Output is correct
48	Correct	350 ms	72884 KB	Output is correct
49	Correct	285 ms	71584 KB	Output is correct
50	Correct	288 ms	43848 KB	Output is correct
51	Correct	241 ms	43992 KB	Output is correct
52	Correct	361 ms	43892 KB	Output is correct
53	Correct	247 ms	44812 KB	Output is correct
54	Correct	359 ms	69812 KB	Output is correct
55	Correct	22 ms	16972 KB	Output is correct
56	Correct	18 ms	16156 KB	Output is correct
57	Correct	92 ms	31876 KB	Output is correct
58	Correct	58 ms	25172 KB	Output is correct
59	Correct	87 ms	43460 KB	Output is correct
60	Correct	269 ms	71876 KB	Output is correct
61	Correct	271 ms	48196 KB	Output is correct
62	Correct	235 ms	44032 KB	Output is correct
63	Correct	302 ms	43972 KB	Output is correct
64	Correct	514 ms	87956 KB	Output is correct
65	Correct	500 ms	81888 KB	Output is correct
66	Correct	291 ms	68644 KB	Output is correct
67	Correct	192 ms	37540 KB	Output is correct
68	Correct	445 ms	55748 KB	Output is correct
69	Correct	427 ms	59972 KB	Output is correct
70	Correct	385 ms	54056 KB	Output is correct

답안 #446435

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