답안 #16516 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16516	2015-08-27T01:10:29 Z	khsoo01	경주 (Race) (IOI11_race)	C++	100 / 100	1247 ms	48368 KB

race

#include<bits/stdc++.h>
#include "race.h"
#define INF 987654321
using namespace std;
vector<int>cg[200005],cv[200005];
stack<int>used;
int ch[200005],p[1000005],n,cn,k,ans=INF;
bool col[200005];

void count_num(int idx,int prev) {
    int i; cn++;
    for(i=0;i<cg[idx].size();i++) {
        if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
            count_num(cg[idx][i],idx);
        }
    }
}

pair<int,int> find_cen(int idx,int prev) {
    pair<int,int> ret(INF,-1),tmp;
    int i,cc=1,mc=0;
    for(i=0;i<cg[idx].size();i++) {
        if(col[cg[idx][i]] || cg[idx][i]==prev) continue;
        tmp=find_cen(cg[idx][i],idx);
        if(tmp.first<ret.first) ret=tmp;
        mc=max(mc,ch[cg[idx][i]]);
        cc+=ch[cg[idx][i]];
    }
    mc=max(mc,cn-cc);
    if(mc<ret.first) ret={mc,idx};
    ch[idx]=cc;
    return ret;
}

void match(int idx,int prev,int cnt,int len) {
    if(len>k) return;
    int i; ans=min(ans,p[k-len]+cnt);
    for(i=0;i<cg[idx].size();i++) {
        if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
            match(cg[idx][i],idx,cnt+1,len+cv[idx][i]);
        }
    }
}

void apply(int idx,int prev,int cnt,int len) {
    if(len>k) return;
    int i; p[len]=min(p[len],cnt); used.push(len);
    for(i=0;i<cg[idx].size();i++) {
        if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
            apply(cg[idx][i],idx,cnt+1,len+cv[idx][i]);
        }
    }
}

void dnc(int idx) {
    while(!used.empty()) {p[used.top()]=INF; used.pop();}
    p[0]=0;
    cn=0; count_num(idx,-1);
    int i,cen=find_cen(idx,-1).second;
    for(i=0;i<cg[cen].size();i++) {
        if(col[cg[cen][i]])continue;
        match(cg[cen][i],cen,1,cv[cen][i]);
        apply(cg[cen][i],cen,1,cv[cen][i]);
    }
    col[cen]=1;
    for(i=0;i<cg[cen].size();i++) {
        if(!col[cg[cen][i]]) {
            dnc(cg[cen][i]);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    int i; n=N; k=K;
    for(i=0;i<n-1;i++) {
        cg[H[i][0]].push_back(H[i][1]);
        cv[H[i][0]].push_back(L[i]);
        cg[H[i][1]].push_back(H[i][0]);
        cv[H[i][1]].push_back(L[i]);
    }
    for(i=1;i<=k;i++)p[i]=INF;
    dnc(0);
    return (ans==INF?-1:ans);
}

Compilation message

race.cpp: In function 'void count_num(int, int)':
race.cpp:12:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'std::pair<int, int> find_cen(int, int)':
race.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'void match(int, int, int, int)':
race.cpp:38:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'void apply(int, int, int, int)':
race.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'void dnc(int)':
race.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[cen].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[cen].size();i++) {
             ~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9724 KB	Output is correct
2	Correct	11 ms	9828 KB	Output is correct
3	Correct	9 ms	9904 KB	Output is correct
4	Correct	11 ms	9904 KB	Output is correct
5	Correct	9 ms	9904 KB	Output is correct
6	Correct	9 ms	9904 KB	Output is correct
7	Correct	9 ms	9904 KB	Output is correct
8	Correct	9 ms	9952 KB	Output is correct
9	Correct	9 ms	9952 KB	Output is correct
10	Correct	9 ms	9952 KB	Output is correct
11	Correct	9 ms	9952 KB	Output is correct
12	Correct	9 ms	9952 KB	Output is correct
13	Correct	9 ms	9952 KB	Output is correct
14	Correct	9 ms	9952 KB	Output is correct
15	Correct	10 ms	10032 KB	Output is correct
16	Correct	9 ms	10032 KB	Output is correct
17	Correct	10 ms	10032 KB	Output is correct
18	Correct	9 ms	10032 KB	Output is correct
19	Correct	275 ms	18300 KB	Output is correct
20	Correct	250 ms	18300 KB	Output is correct
21	Correct	286 ms	18300 KB	Output is correct
22	Correct	260 ms	18524 KB	Output is correct
23	Correct	178 ms	18524 KB	Output is correct
24	Correct	117 ms	18524 KB	Output is correct
25	Correct	263 ms	22908 KB	Output is correct
26	Correct	174 ms	27724 KB	Output is correct
27	Correct	366 ms	27724 KB	Output is correct
28	Correct	703 ms	44684 KB	Output is correct
29	Correct	669 ms	44684 KB	Output is correct
30	Correct	426 ms	44684 KB	Output is correct
31	Correct	380 ms	44684 KB	Output is correct
32	Correct	469 ms	44684 KB	Output is correct
33	Correct	557 ms	44684 KB	Output is correct
34	Correct	566 ms	44684 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9724 KB	Output is correct
2	Correct	11 ms	9828 KB	Output is correct
3	Correct	9 ms	9904 KB	Output is correct
4	Correct	11 ms	9904 KB	Output is correct
5	Correct	9 ms	9904 KB	Output is correct
6	Correct	9 ms	9904 KB	Output is correct
7	Correct	9 ms	9904 KB	Output is correct
8	Correct	9 ms	9952 KB	Output is correct
9	Correct	9 ms	9952 KB	Output is correct
10	Correct	9 ms	9952 KB	Output is correct
11	Correct	9 ms	9952 KB	Output is correct
12	Correct	9 ms	9952 KB	Output is correct
13	Correct	9 ms	9952 KB	Output is correct
14	Correct	9 ms	9952 KB	Output is correct
15	Correct	10 ms	10032 KB	Output is correct
16	Correct	9 ms	10032 KB	Output is correct
17	Correct	10 ms	10032 KB	Output is correct
18	Correct	9 ms	10032 KB	Output is correct
19	Correct	9 ms	10032 KB	Output is correct
20	Correct	9 ms	10032 KB	Output is correct
21	Correct	10 ms	10108 KB	Output is correct
22	Correct	13 ms	13692 KB	Output is correct
23	Correct	12 ms	13692 KB	Output is correct
24	Correct	15 ms	13692 KB	Output is correct
25	Correct	15 ms	13692 KB	Output is correct
26	Correct	13 ms	13692 KB	Output is correct
27	Correct	13 ms	13692 KB	Output is correct
28	Correct	13 ms	13692 KB	Output is correct
29	Correct	13 ms	13692 KB	Output is correct
30	Correct	13 ms	13692 KB	Output is correct
31	Correct	12 ms	13692 KB	Output is correct
32	Correct	14 ms	13692 KB	Output is correct
33	Correct	12 ms	13692 KB	Output is correct
34	Correct	13 ms	13692 KB	Output is correct
35	Correct	13 ms	13692 KB	Output is correct
36	Correct	13 ms	13692 KB	Output is correct
37	Correct	12 ms	13692 KB	Output is correct
38	Correct	13 ms	13692 KB	Output is correct
39	Correct	275 ms	18300 KB	Output is correct
40	Correct	250 ms	18300 KB	Output is correct
41	Correct	286 ms	18300 KB	Output is correct
42	Correct	260 ms	18524 KB	Output is correct
43	Correct	178 ms	18524 KB	Output is correct
44	Correct	117 ms	18524 KB	Output is correct
45	Correct	263 ms	22908 KB	Output is correct
46	Correct	174 ms	27724 KB	Output is correct
47	Correct	366 ms	27724 KB	Output is correct
48	Correct	703 ms	44684 KB	Output is correct
49	Correct	669 ms	44684 KB	Output is correct
50	Correct	426 ms	44684 KB	Output is correct
51	Correct	380 ms	44684 KB	Output is correct
52	Correct	469 ms	44684 KB	Output is correct
53	Correct	557 ms	44684 KB	Output is correct
54	Correct	566 ms	44684 KB	Output is correct
55	Correct	27 ms	44684 KB	Output is correct
56	Correct	27 ms	44684 KB	Output is correct
57	Correct	138 ms	44684 KB	Output is correct
58	Correct	67 ms	44684 KB	Output is correct
59	Correct	265 ms	44684 KB	Output is correct
60	Correct	1247 ms	48368 KB	Output is correct
61	Correct	451 ms	48368 KB	Output is correct
62	Correct	489 ms	48368 KB	Output is correct
63	Correct	627 ms	48368 KB	Output is correct
64	Correct	1213 ms	48368 KB	Output is correct
65	Correct	606 ms	48368 KB	Output is correct
66	Correct	986 ms	48368 KB	Output is correct
67	Correct	274 ms	48368 KB	Output is correct
68	Correct	579 ms	48368 KB	Output is correct
69	Correct	630 ms	48368 KB	Output is correct
70	Correct	693 ms	48368 KB	Output is correct

답안 #16516

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