답안 #34569 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34569	2017-11-12T16:22:16 Z	top34051	경주 (Race) (IOI11_race)	C++14	100 / 100	897 ms	58620 KB

race

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

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 200005;
const int inf = 1e6;

int n,k,ans;
int cur, h[maxn], sz[maxn], st[maxn], ft[maxn], p[maxn];
long long sum[maxn];
vector<int> go[maxn];
vector<pii> edge[maxn];
map<long long,int> s;

void dfs(int u,int last) {
    st[u] = ++cur; p[cur] = u;
    sz[u] = 1; h[u] = h[last]+1;
    for(auto t : edge[u]) {
        int v = t.X, val = t.Y;
        if(v!=last) {
            sum[v] = sum[u] + val;
            dfs(v,u);
            sz[u] += sz[v];
        }
    }
    ft[u] = cur;
//    printf("%d : [%d, %d]   h = %d   sz = %d   sum = %lld\n",u,st[u],ft[u],h[u],sz[u],sum[u]);
}

void add(long long x,int val) {
    if(s.find(x)==s.end()) s[x] = val;
    else s[x] = min(s[x],val);
}

int get(long long x) {
    if(s.find(x)==s.end()) return inf;
    return s[x];
}

void solve(int u,int last,int keep) {
    int mx = 0, big = -1;
    for(auto v : go[u]) if(v!=last && sz[v]>mx) mx = sz[v], big = v;
    for(auto v : go[u]) if(v!=last && v!=big) solve(v,u,0);
    if(big!=-1) solve(big,u,1);
    //solve
//    printf("solve %d\n",u);
    add(sum[u],h[u]);
    ans = min(ans,get(k+sum[u])-h[u]);
    for(auto v : go[u]) {
        if(v!=last && v!=big) {
            for(int i=st[v];i<=ft[v];i++) {
//                printf("\ttry %d : (%lld) : want %lld\n",p[i],sum[p[i]],k-sum[p[i]]+2*sum[u]);
                ans = min(ans,get(k-sum[p[i]]+2*sum[u])+h[p[i]]-2*h[u]);
            }
            for(int i=st[v];i<=ft[v];i++) add(sum[p[i]],h[p[i]]);
        }
    }
    //delete
    if(!keep) s.clear();
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for(int i=0;i<N-1;i++) {
        int x = H[i][0]+1, y = H[i][1]+1, val = L[i];
        edge[x].push_back({y,val}); edge[y].push_back({x,val});
        go[x].push_back(y); go[y].push_back(x);
    }
    dfs(1,0);
    ans = inf;
    solve(1,0,0);
    if(ans>n) return -1;
    return ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Output is correct
2	Correct	11 ms	9964 KB	Output is correct
3	Correct	11 ms	10012 KB	Output is correct
4	Correct	11 ms	10012 KB	Output is correct
5	Correct	11 ms	10012 KB	Output is correct
6	Correct	9 ms	10012 KB	Output is correct
7	Correct	9 ms	10012 KB	Output is correct
8	Correct	9 ms	10012 KB	Output is correct
9	Correct	10 ms	10012 KB	Output is correct
10	Correct	9 ms	10012 KB	Output is correct
11	Correct	9 ms	10016 KB	Output is correct
12	Correct	9 ms	10016 KB	Output is correct
13	Correct	9 ms	10016 KB	Output is correct
14	Correct	9 ms	10068 KB	Output is correct
15	Correct	10 ms	10068 KB	Output is correct
16	Correct	10 ms	10068 KB	Output is correct
17	Correct	10 ms	10068 KB	Output is correct
18	Correct	8 ms	10068 KB	Output is correct
19	Correct	221 ms	20932 KB	Output is correct
20	Correct	229 ms	20988 KB	Output is correct
21	Correct	224 ms	20988 KB	Output is correct
22	Correct	214 ms	20988 KB	Output is correct
23	Correct	284 ms	21116 KB	Output is correct
24	Correct	229 ms	21116 KB	Output is correct
25	Correct	199 ms	24828 KB	Output is correct
26	Correct	93 ms	27948 KB	Output is correct
27	Correct	424 ms	32512 KB	Output is correct
28	Correct	480 ms	58620 KB	Output is correct
29	Correct	548 ms	58620 KB	Output is correct
30	Correct	365 ms	58620 KB	Output is correct
31	Correct	366 ms	58620 KB	Output is correct
32	Correct	496 ms	58620 KB	Output is correct
33	Correct	531 ms	58620 KB	Output is correct
34	Correct	721 ms	58620 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Output is correct
2	Correct	11 ms	9964 KB	Output is correct
3	Correct	11 ms	10012 KB	Output is correct
4	Correct	11 ms	10012 KB	Output is correct
5	Correct	11 ms	10012 KB	Output is correct
6	Correct	9 ms	10012 KB	Output is correct
7	Correct	9 ms	10012 KB	Output is correct
8	Correct	9 ms	10012 KB	Output is correct
9	Correct	10 ms	10012 KB	Output is correct
10	Correct	9 ms	10012 KB	Output is correct
11	Correct	9 ms	10016 KB	Output is correct
12	Correct	9 ms	10016 KB	Output is correct
13	Correct	9 ms	10016 KB	Output is correct
14	Correct	9 ms	10068 KB	Output is correct
15	Correct	10 ms	10068 KB	Output is correct
16	Correct	10 ms	10068 KB	Output is correct
17	Correct	10 ms	10068 KB	Output is correct
18	Correct	8 ms	10068 KB	Output is correct
19	Correct	9 ms	10068 KB	Output is correct
20	Correct	9 ms	10068 KB	Output is correct
21	Correct	11 ms	10108 KB	Output is correct
22	Correct	10 ms	10236 KB	Output is correct
23	Correct	10 ms	10236 KB	Output is correct
24	Correct	10 ms	10236 KB	Output is correct
25	Correct	12 ms	10236 KB	Output is correct
26	Correct	16 ms	10236 KB	Output is correct
27	Correct	10 ms	10236 KB	Output is correct
28	Correct	10 ms	10288 KB	Output is correct
29	Correct	11 ms	10288 KB	Output is correct
30	Correct	10 ms	10288 KB	Output is correct
31	Correct	10 ms	10288 KB	Output is correct
32	Correct	9 ms	10288 KB	Output is correct
33	Correct	10 ms	10288 KB	Output is correct
34	Correct	9 ms	10288 KB	Output is correct
35	Correct	10 ms	10288 KB	Output is correct
36	Correct	10 ms	10288 KB	Output is correct
37	Correct	10 ms	10288 KB	Output is correct
38	Correct	10 ms	10288 KB	Output is correct
39	Correct	221 ms	20932 KB	Output is correct
40	Correct	229 ms	20988 KB	Output is correct
41	Correct	224 ms	20988 KB	Output is correct
42	Correct	214 ms	20988 KB	Output is correct
43	Correct	284 ms	21116 KB	Output is correct
44	Correct	229 ms	21116 KB	Output is correct
45	Correct	199 ms	24828 KB	Output is correct
46	Correct	93 ms	27948 KB	Output is correct
47	Correct	424 ms	32512 KB	Output is correct
48	Correct	480 ms	58620 KB	Output is correct
49	Correct	548 ms	58620 KB	Output is correct
50	Correct	365 ms	58620 KB	Output is correct
51	Correct	366 ms	58620 KB	Output is correct
52	Correct	496 ms	58620 KB	Output is correct
53	Correct	531 ms	58620 KB	Output is correct
54	Correct	721 ms	58620 KB	Output is correct
55	Correct	27 ms	58620 KB	Output is correct
56	Correct	19 ms	58620 KB	Output is correct
57	Correct	140 ms	58620 KB	Output is correct
58	Correct	83 ms	58620 KB	Output is correct
59	Correct	177 ms	58620 KB	Output is correct
60	Correct	492 ms	58620 KB	Output is correct
61	Correct	447 ms	58620 KB	Output is correct
62	Correct	387 ms	58620 KB	Output is correct
63	Correct	438 ms	58620 KB	Output is correct
64	Correct	760 ms	58620 KB	Output is correct
65	Correct	897 ms	58620 KB	Output is correct
66	Correct	577 ms	58620 KB	Output is correct
67	Correct	392 ms	58620 KB	Output is correct
68	Correct	692 ms	58620 KB	Output is correct
69	Correct	645 ms	58620 KB	Output is correct
70	Correct	651 ms	58620 KB	Output is correct

답안 #34569

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