답안 #374248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374248	2021-03-07T00:51:51 Z	ijxjdjd	경주 (Race) (IOI11_race)	C++14	100 / 100	568 ms	89116 KB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = (int)(2e5 + 5);
ll K;
vector<pair<int, int>> adj[MAXN];
struct paths {
    ll addL = 0;
    int addV = 0;
    unordered_map<ll, int> mn;
    paths() {
        mn[0] = 0;
    }
    bool contains(ll a) {
        return mn.count(a-addL);
    }
    int get(ll a) {
        if (!contains(a)) {
            return 2*MAXN;
        }
        return mn[a-addL] + addV;
    }
    void insert(ll v, int cnt) {
        if(get(v) > cnt) {
            mn[v-addL] = cnt-addV;
        }
    }
    int size() {
        return mn.size();
    }
};
paths keep[MAXN];
int res = MAXN;
void dfs(int n, int p) {
    for (auto& e : adj[n]) {
        if (e.first != p) {
            dfs(e.first, n);
            keep[e.first].addL += e.second;
            keep[e.first].addV++;
            if (keep[n].size() < keep[e.first].size()) {
                swap(keep[e.first], keep[n]);
            }
            for (auto& keypair : keep[e.first].mn) {
                ll od = keypair.first + keep[e.first].addL;
                if (keep[n].contains(K-od)) {
                    res = min(keypair.second + keep[e.first].addV + keep[n].get(K-od), res);
                }
            }
            for (auto& keypair : keep[e.first].mn) {
                keep[n].insert(keypair.first + keep[e.first].addL, keypair.second + keep[e.first].addV);
            }
        }
    }
}
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);
    return (res == MAXN ? -1 : res);
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	31724 KB	Output is correct
2	Correct	49 ms	31724 KB	Output is correct
3	Correct	48 ms	31724 KB	Output is correct
4	Correct	47 ms	31724 KB	Output is correct
5	Correct	47 ms	31724 KB	Output is correct
6	Correct	49 ms	31724 KB	Output is correct
7	Correct	49 ms	31724 KB	Output is correct
8	Correct	48 ms	31724 KB	Output is correct
9	Correct	48 ms	31724 KB	Output is correct
10	Correct	49 ms	31724 KB	Output is correct
11	Correct	49 ms	31724 KB	Output is correct
12	Correct	48 ms	31724 KB	Output is correct
13	Correct	48 ms	31724 KB	Output is correct
14	Correct	48 ms	31724 KB	Output is correct
15	Correct	47 ms	31724 KB	Output is correct
16	Correct	47 ms	31724 KB	Output is correct
17	Correct	47 ms	31724 KB	Output is correct
18	Correct	48 ms	31724 KB	Output is correct
19	Correct	50 ms	31724 KB	Output is correct
20	Correct	48 ms	31596 KB	Output is correct
21	Correct	48 ms	31724 KB	Output is correct
22	Correct	49 ms	31852 KB	Output is correct
23	Correct	49 ms	31852 KB	Output is correct
24	Correct	49 ms	31852 KB	Output is correct
25	Correct	52 ms	31852 KB	Output is correct
26	Correct	49 ms	31852 KB	Output is correct
27	Correct	48 ms	31724 KB	Output is correct
28	Correct	50 ms	31836 KB	Output is correct
29	Correct	49 ms	31852 KB	Output is correct
30	Correct	49 ms	31852 KB	Output is correct
31	Correct	48 ms	31852 KB	Output is correct
32	Correct	49 ms	31852 KB	Output is correct
33	Correct	49 ms	31980 KB	Output is correct
34	Correct	49 ms	31852 KB	Output is correct
35	Correct	48 ms	31852 KB	Output is correct
36	Correct	49 ms	31852 KB	Output is correct
37	Correct	48 ms	31724 KB	Output is correct
38	Correct	48 ms	31852 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	31724 KB	Output is correct
2	Correct	49 ms	31724 KB	Output is correct
3	Correct	48 ms	31724 KB	Output is correct
4	Correct	47 ms	31724 KB	Output is correct
5	Correct	47 ms	31724 KB	Output is correct
6	Correct	49 ms	31724 KB	Output is correct
7	Correct	49 ms	31724 KB	Output is correct
8	Correct	48 ms	31724 KB	Output is correct
9	Correct	48 ms	31724 KB	Output is correct
10	Correct	49 ms	31724 KB	Output is correct
11	Correct	49 ms	31724 KB	Output is correct
12	Correct	48 ms	31724 KB	Output is correct
13	Correct	48 ms	31724 KB	Output is correct
14	Correct	48 ms	31724 KB	Output is correct
15	Correct	47 ms	31724 KB	Output is correct
16	Correct	47 ms	31724 KB	Output is correct
17	Correct	47 ms	31724 KB	Output is correct
18	Correct	48 ms	31724 KB	Output is correct
19	Correct	177 ms	42660 KB	Output is correct
20	Correct	178 ms	42560 KB	Output is correct
21	Correct	172 ms	42432 KB	Output is correct
22	Correct	177 ms	43664 KB	Output is correct
23	Correct	204 ms	52588 KB	Output is correct
24	Correct	160 ms	45932 KB	Output is correct
25	Correct	157 ms	47852 KB	Output is correct
26	Correct	113 ms	56044 KB	Output is correct
27	Correct	253 ms	49004 KB	Output is correct
28	Correct	348 ms	89116 KB	Output is correct
29	Correct	354 ms	87256 KB	Output is correct
30	Correct	256 ms	49004 KB	Output is correct
31	Correct	249 ms	49132 KB	Output is correct
32	Correct	330 ms	49276 KB	Output is correct
33	Correct	312 ms	52144 KB	Output is correct
34	Correct	502 ms	74548 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	31724 KB	Output is correct
2	Correct	49 ms	31724 KB	Output is correct
3	Correct	48 ms	31724 KB	Output is correct
4	Correct	47 ms	31724 KB	Output is correct
5	Correct	47 ms	31724 KB	Output is correct
6	Correct	49 ms	31724 KB	Output is correct
7	Correct	49 ms	31724 KB	Output is correct
8	Correct	48 ms	31724 KB	Output is correct
9	Correct	48 ms	31724 KB	Output is correct
10	Correct	49 ms	31724 KB	Output is correct
11	Correct	49 ms	31724 KB	Output is correct
12	Correct	48 ms	31724 KB	Output is correct
13	Correct	48 ms	31724 KB	Output is correct
14	Correct	48 ms	31724 KB	Output is correct
15	Correct	47 ms	31724 KB	Output is correct
16	Correct	47 ms	31724 KB	Output is correct
17	Correct	47 ms	31724 KB	Output is correct
18	Correct	48 ms	31724 KB	Output is correct
19	Correct	50 ms	31724 KB	Output is correct
20	Correct	48 ms	31596 KB	Output is correct
21	Correct	48 ms	31724 KB	Output is correct
22	Correct	49 ms	31852 KB	Output is correct
23	Correct	49 ms	31852 KB	Output is correct
24	Correct	49 ms	31852 KB	Output is correct
25	Correct	52 ms	31852 KB	Output is correct
26	Correct	49 ms	31852 KB	Output is correct
27	Correct	48 ms	31724 KB	Output is correct
28	Correct	50 ms	31836 KB	Output is correct
29	Correct	49 ms	31852 KB	Output is correct
30	Correct	49 ms	31852 KB	Output is correct
31	Correct	48 ms	31852 KB	Output is correct
32	Correct	49 ms	31852 KB	Output is correct
33	Correct	49 ms	31980 KB	Output is correct
34	Correct	49 ms	31852 KB	Output is correct
35	Correct	48 ms	31852 KB	Output is correct
36	Correct	49 ms	31852 KB	Output is correct
37	Correct	48 ms	31724 KB	Output is correct
38	Correct	48 ms	31852 KB	Output is correct
39	Correct	177 ms	42660 KB	Output is correct
40	Correct	178 ms	42560 KB	Output is correct
41	Correct	172 ms	42432 KB	Output is correct
42	Correct	177 ms	43664 KB	Output is correct
43	Correct	204 ms	52588 KB	Output is correct
44	Correct	160 ms	45932 KB	Output is correct
45	Correct	157 ms	47852 KB	Output is correct
46	Correct	113 ms	56044 KB	Output is correct
47	Correct	253 ms	49004 KB	Output is correct
48	Correct	348 ms	89116 KB	Output is correct
49	Correct	354 ms	87256 KB	Output is correct
50	Correct	256 ms	49004 KB	Output is correct
51	Correct	249 ms	49132 KB	Output is correct
52	Correct	330 ms	49276 KB	Output is correct
53	Correct	312 ms	52144 KB	Output is correct
54	Correct	502 ms	74548 KB	Output is correct
55	Correct	60 ms	33516 KB	Output is correct
56	Correct	56 ms	32748 KB	Output is correct
57	Correct	117 ms	42092 KB	Output is correct
58	Correct	88 ms	37856 KB	Output is correct
59	Correct	123 ms	60304 KB	Output is correct
60	Correct	342 ms	87544 KB	Output is correct
61	Correct	267 ms	51308 KB	Output is correct
62	Correct	250 ms	49108 KB	Output is correct
63	Correct	320 ms	49260 KB	Output is correct
64	Correct	562 ms	86544 KB	Output is correct
65	Correct	568 ms	85044 KB	Output is correct
66	Correct	358 ms	82228 KB	Output is correct
67	Correct	207 ms	45660 KB	Output is correct
68	Correct	387 ms	61236 KB	Output is correct
69	Correct	408 ms	64820 KB	Output is correct
70	Correct	368 ms	60212 KB	Output is correct

답안 #374248

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