답안 #81767 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81767	2018-10-26T13:22:05 Z	chelly	경주 (Race) (IOI11_race)	C++11	100 / 100	1909 ms	107748 KB

race

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
const int MAXN = 200005, INF = 0x3f3f3f3f;

int N, K, H[MAXN][2], L[MAXN];
int sz[MAXN];
map<int, int> best;
bool done[MAXN];
vector<pii> adj[MAXN];
queue<pii> ar;
int ans = INF, target;
void dfs (int u, int p){
    sz[u]=1;
    for (pii e: adj[u]){
        if (e.first==p||done[e.first]) continue;
        dfs(e.first, u);
        sz[u]+=sz[e.first];
    }
}
int centroid (int u, int p, int S){
    for (pii e: adj[u]){
        if (sz[e.first]*2>S&&e.first!=p&&!done[e.first]) return centroid(e.first, u, S);
    }
    return u;
}
void path (int u, int p, int length, int cnt){
    if (length==target) ans = min(ans, cnt);
    else{
        ar.push(mp(length, cnt));
        if (best[target-length]!=0) ans = min(ans, best[target-length]+cnt);
    }
    for (pii e: adj[u]){
        if (e.first!=p&&!done[e.first]) path (e.first, u, length+e.second, cnt+1);
    }
}
void solve(int u){
    dfs(u, -1);
    u = centroid(u, -1, sz[u]);
    //cout<<u<<endl;
    best.clear();
    done[u] = true;
    for (pii e: adj[u]){
        if (done[e.first]) continue;
        path (e.first, u, e.second, 1);
        while (!ar.empty()){
            pii p = ar.front();
            ar.pop();
            if (best[p.first]==0) best[p.first] = p.second;
            else best[p.first] = min(best[p.first], p.second);
        }
    }
    for (pii e: adj[u]){
        if(!done[e.first]) solve(e.first);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    target = K;
    for (int i = 0; i<N-1; i++){
        adj[H[i][0]].pb(mp(H[i][1], L[i]));
        adj[H[i][1]].pb(mp(H[i][0], L[i]));
    }
    solve (0);
    return ans==INF?-1:ans;
}
/*
int main()
{
    cin>>N>>K;
    for (int i = 0; i<N-1; i++){
        scanf("%d%d%d", &H[i][0], &H[i][1], &L[i]);
    }
    cout<<best_path(N, K, H, L);
}*/

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	8 ms	5224 KB	Output is correct
3	Correct	6 ms	5224 KB	Output is correct
4	Correct	6 ms	5224 KB	Output is correct
5	Correct	6 ms	5244 KB	Output is correct
6	Correct	6 ms	5276 KB	Output is correct
7	Correct	6 ms	5280 KB	Output is correct
8	Correct	6 ms	5280 KB	Output is correct
9	Correct	6 ms	5316 KB	Output is correct
10	Correct	7 ms	5348 KB	Output is correct
11	Correct	6 ms	5348 KB	Output is correct
12	Correct	6 ms	5376 KB	Output is correct
13	Correct	7 ms	5376 KB	Output is correct
14	Correct	6 ms	5376 KB	Output is correct
15	Correct	7 ms	5376 KB	Output is correct
16	Correct	6 ms	5376 KB	Output is correct
17	Correct	7 ms	5376 KB	Output is correct
18	Correct	6 ms	5376 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	8 ms	5224 KB	Output is correct
3	Correct	6 ms	5224 KB	Output is correct
4	Correct	6 ms	5224 KB	Output is correct
5	Correct	6 ms	5244 KB	Output is correct
6	Correct	6 ms	5276 KB	Output is correct
7	Correct	6 ms	5280 KB	Output is correct
8	Correct	6 ms	5280 KB	Output is correct
9	Correct	6 ms	5316 KB	Output is correct
10	Correct	7 ms	5348 KB	Output is correct
11	Correct	6 ms	5348 KB	Output is correct
12	Correct	6 ms	5376 KB	Output is correct
13	Correct	7 ms	5376 KB	Output is correct
14	Correct	6 ms	5376 KB	Output is correct
15	Correct	7 ms	5376 KB	Output is correct
16	Correct	6 ms	5376 KB	Output is correct
17	Correct	7 ms	5376 KB	Output is correct
18	Correct	6 ms	5376 KB	Output is correct
19	Correct	6 ms	5376 KB	Output is correct
20	Correct	6 ms	5376 KB	Output is correct
21	Correct	8 ms	5452 KB	Output is correct
22	Correct	9 ms	5592 KB	Output is correct
23	Correct	9 ms	5624 KB	Output is correct
24	Correct	12 ms	5656 KB	Output is correct
25	Correct	8 ms	5688 KB	Output is correct
26	Correct	8 ms	5704 KB	Output is correct
27	Correct	7 ms	5704 KB	Output is correct
28	Correct	8 ms	5736 KB	Output is correct
29	Correct	8 ms	5768 KB	Output is correct
30	Correct	8 ms	5784 KB	Output is correct
31	Correct	8 ms	5788 KB	Output is correct
32	Correct	8 ms	5816 KB	Output is correct
33	Correct	9 ms	5820 KB	Output is correct
34	Correct	8 ms	5820 KB	Output is correct
35	Correct	8 ms	5864 KB	Output is correct
36	Correct	9 ms	5876 KB	Output is correct
37	Correct	8 ms	5876 KB	Output is correct
38	Correct	9 ms	5900 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	8 ms	5224 KB	Output is correct
3	Correct	6 ms	5224 KB	Output is correct
4	Correct	6 ms	5224 KB	Output is correct
5	Correct	6 ms	5244 KB	Output is correct
6	Correct	6 ms	5276 KB	Output is correct
7	Correct	6 ms	5280 KB	Output is correct
8	Correct	6 ms	5280 KB	Output is correct
9	Correct	6 ms	5316 KB	Output is correct
10	Correct	7 ms	5348 KB	Output is correct
11	Correct	6 ms	5348 KB	Output is correct
12	Correct	6 ms	5376 KB	Output is correct
13	Correct	7 ms	5376 KB	Output is correct
14	Correct	6 ms	5376 KB	Output is correct
15	Correct	7 ms	5376 KB	Output is correct
16	Correct	6 ms	5376 KB	Output is correct
17	Correct	7 ms	5376 KB	Output is correct
18	Correct	6 ms	5376 KB	Output is correct
19	Correct	354 ms	12824 KB	Output is correct
20	Correct	350 ms	14104 KB	Output is correct
21	Correct	336 ms	15528 KB	Output is correct
22	Correct	287 ms	16880 KB	Output is correct
23	Correct	556 ms	18748 KB	Output is correct
24	Correct	236 ms	19828 KB	Output is correct
25	Correct	309 ms	25812 KB	Output is correct
26	Correct	197 ms	28244 KB	Output is correct
27	Correct	477 ms	30844 KB	Output is correct
28	Correct	1545 ms	63360 KB	Output is correct
29	Correct	1596 ms	65492 KB	Output is correct
30	Correct	480 ms	65492 KB	Output is correct
31	Correct	503 ms	65492 KB	Output is correct
32	Correct	599 ms	65492 KB	Output is correct
33	Correct	930 ms	65492 KB	Output is correct
34	Correct	1712 ms	69788 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	8 ms	5224 KB	Output is correct
3	Correct	6 ms	5224 KB	Output is correct
4	Correct	6 ms	5224 KB	Output is correct
5	Correct	6 ms	5244 KB	Output is correct
6	Correct	6 ms	5276 KB	Output is correct
7	Correct	6 ms	5280 KB	Output is correct
8	Correct	6 ms	5280 KB	Output is correct
9	Correct	6 ms	5316 KB	Output is correct
10	Correct	7 ms	5348 KB	Output is correct
11	Correct	6 ms	5348 KB	Output is correct
12	Correct	6 ms	5376 KB	Output is correct
13	Correct	7 ms	5376 KB	Output is correct
14	Correct	6 ms	5376 KB	Output is correct
15	Correct	7 ms	5376 KB	Output is correct
16	Correct	6 ms	5376 KB	Output is correct
17	Correct	7 ms	5376 KB	Output is correct
18	Correct	6 ms	5376 KB	Output is correct
19	Correct	6 ms	5376 KB	Output is correct
20	Correct	6 ms	5376 KB	Output is correct
21	Correct	8 ms	5452 KB	Output is correct
22	Correct	9 ms	5592 KB	Output is correct
23	Correct	9 ms	5624 KB	Output is correct
24	Correct	12 ms	5656 KB	Output is correct
25	Correct	8 ms	5688 KB	Output is correct
26	Correct	8 ms	5704 KB	Output is correct
27	Correct	7 ms	5704 KB	Output is correct
28	Correct	8 ms	5736 KB	Output is correct
29	Correct	8 ms	5768 KB	Output is correct
30	Correct	8 ms	5784 KB	Output is correct
31	Correct	8 ms	5788 KB	Output is correct
32	Correct	8 ms	5816 KB	Output is correct
33	Correct	9 ms	5820 KB	Output is correct
34	Correct	8 ms	5820 KB	Output is correct
35	Correct	8 ms	5864 KB	Output is correct
36	Correct	9 ms	5876 KB	Output is correct
37	Correct	8 ms	5876 KB	Output is correct
38	Correct	9 ms	5900 KB	Output is correct
39	Correct	354 ms	12824 KB	Output is correct
40	Correct	350 ms	14104 KB	Output is correct
41	Correct	336 ms	15528 KB	Output is correct
42	Correct	287 ms	16880 KB	Output is correct
43	Correct	556 ms	18748 KB	Output is correct
44	Correct	236 ms	19828 KB	Output is correct
45	Correct	309 ms	25812 KB	Output is correct
46	Correct	197 ms	28244 KB	Output is correct
47	Correct	477 ms	30844 KB	Output is correct
48	Correct	1545 ms	63360 KB	Output is correct
49	Correct	1596 ms	65492 KB	Output is correct
50	Correct	480 ms	65492 KB	Output is correct
51	Correct	503 ms	65492 KB	Output is correct
52	Correct	599 ms	65492 KB	Output is correct
53	Correct	930 ms	65492 KB	Output is correct
54	Correct	1712 ms	69788 KB	Output is correct
55	Correct	42 ms	69788 KB	Output is correct
56	Correct	26 ms	69788 KB	Output is correct
57	Correct	225 ms	69788 KB	Output is correct
58	Correct	65 ms	69788 KB	Output is correct
59	Correct	543 ms	69788 KB	Output is correct
60	Correct	1722 ms	86072 KB	Output is correct
61	Correct	614 ms	86072 KB	Output is correct
62	Correct	503 ms	86072 KB	Output is correct
63	Correct	588 ms	86072 KB	Output is correct
64	Correct	1909 ms	86072 KB	Output is correct
65	Correct	1629 ms	94064 KB	Output is correct
66	Correct	1700 ms	105888 KB	Output is correct
67	Correct	191 ms	105888 KB	Output is correct
68	Correct	859 ms	105888 KB	Output is correct
69	Correct	892 ms	105888 KB	Output is correct
70	Correct	785 ms	107748 KB	Output is correct

답안 #81767

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