답안 #543173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543173	2022-03-29T15:43:04 Z	__Variatto	경주 (Race) (IOI11_race)	C++17	100 / 100	666 ms	59448 KB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e5+10, MAXV=1e6+10;
vector<pair<int,int>>g[MAXV];
int n, k, centr, podd[MAXV], o[MAXV];
int odw[MAXV], wynik=MAXV, mini[MAXV];
void dfs(int v, int oj, int roz){
    podd[v]=1, o[v]=oj;
    int maxi=0;
    for(auto s:g[v]){
        if(s.fi!=oj && !odw[s.fi]){
            dfs(s.fi, v, roz);
            maxi=max(maxi, podd[s.fi]);
            podd[v]+=podd[s.fi];
        }
    }
    if(maxi<=roz/2 && (roz-podd[v])<=roz/2)
        centr=v;
}
void zlicz(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    wynik=min(wynik, mini[k-akt]+ile);
    for(auto s:g[v]){
        if(s.fi==oj||odw[s.fi]<=st) continue;
        zlicz(s.fi, v, st, akt+s.se, ile+1);
    }
}
void dodaj(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    mini[akt]=min(mini[akt], ile);
    for(auto s:g[v]){
        if(s.fi==oj||odw[s.fi]<=st) continue;
        dodaj(s.fi, v, st, akt+s.se, ile+1);
    }
}
void zeruj(int v, int oj, int st, int akt, int ile){
    if(akt>k) return;
    mini[akt]=MAXV;
    for(auto s:g[v]){
        if(s.fi==oj||odw[s.fi]<=st) continue;
        zeruj(s.fi, v, st, akt+s.se, ile+1);
    }
}
void rek(int aktc, int roz, int st){
    odw[aktc]=st;
    for(auto s:g[aktc]){
        if(!odw[s.fi]){
            int newR=podd[s.fi];
            if(s.fi==o[aktc]) newR=roz-podd[aktc];
            centr=0;
            dfs(s.fi, s.fi, newR);
            rek(centr, newR, st+1);
        }
    }
    mini[0]=0;
    for(auto s: g[aktc]){
        if(odw[s.fi]<=st) continue;
        zlicz(s.fi, s.fi, st, s.se, 2);
        dodaj(s.fi, s.fi, st, s.se, 1);
    }
    for(auto s: g[aktc]){
        if(odw[s.fi]<=st) continue;
        zeruj(s.fi, s.fi, st, s.se, 1);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    n=N, k=K;
    for(int i=0; i<n-1; i++)
        g[H[i][0]].pb({H[i][1], L[i]}), g[H[i][1]].pb({H[i][0], L[i]});
    for(int i=0; i<=k; i++)
        mini[i]=MAXV;
    dfs(0, 0, n);
    rek(centr, n, 1);
    if(wynik==MAXV) wynik=0;
    return wynik-1;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	11 ms	23844 KB	Output is correct
4	Correct	13 ms	23824 KB	Output is correct
5	Correct	15 ms	23892 KB	Output is correct
6	Correct	12 ms	23812 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	13 ms	23808 KB	Output is correct
12	Correct	15 ms	23788 KB	Output is correct
13	Correct	16 ms	23764 KB	Output is correct
14	Correct	14 ms	23740 KB	Output is correct
15	Correct	13 ms	23800 KB	Output is correct
16	Correct	12 ms	23748 KB	Output is correct
17	Correct	13 ms	23740 KB	Output is correct
18	Correct	13 ms	23764 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	11 ms	23844 KB	Output is correct
4	Correct	13 ms	23824 KB	Output is correct
5	Correct	15 ms	23892 KB	Output is correct
6	Correct	12 ms	23812 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	13 ms	23808 KB	Output is correct
12	Correct	15 ms	23788 KB	Output is correct
13	Correct	16 ms	23764 KB	Output is correct
14	Correct	14 ms	23740 KB	Output is correct
15	Correct	13 ms	23800 KB	Output is correct
16	Correct	12 ms	23748 KB	Output is correct
17	Correct	13 ms	23740 KB	Output is correct
18	Correct	13 ms	23764 KB	Output is correct
19	Correct	13 ms	23764 KB	Output is correct
20	Correct	13 ms	23764 KB	Output is correct
21	Correct	13 ms	23892 KB	Output is correct
22	Correct	15 ms	27400 KB	Output is correct
23	Correct	15 ms	26836 KB	Output is correct
24	Correct	16 ms	27220 KB	Output is correct
25	Correct	15 ms	27160 KB	Output is correct
26	Correct	15 ms	25208 KB	Output is correct
27	Correct	16 ms	26964 KB	Output is correct
28	Correct	14 ms	24624 KB	Output is correct
29	Correct	15 ms	25052 KB	Output is correct
30	Correct	16 ms	25332 KB	Output is correct
31	Correct	14 ms	26324 KB	Output is correct
32	Correct	14 ms	26580 KB	Output is correct
33	Correct	15 ms	26836 KB	Output is correct
34	Correct	15 ms	26112 KB	Output is correct
35	Correct	14 ms	27052 KB	Output is correct
36	Correct	15 ms	27500 KB	Output is correct
37	Correct	14 ms	26976 KB	Output is correct
38	Correct	14 ms	25812 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	11 ms	23844 KB	Output is correct
4	Correct	13 ms	23824 KB	Output is correct
5	Correct	15 ms	23892 KB	Output is correct
6	Correct	12 ms	23812 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	13 ms	23808 KB	Output is correct
12	Correct	15 ms	23788 KB	Output is correct
13	Correct	16 ms	23764 KB	Output is correct
14	Correct	14 ms	23740 KB	Output is correct
15	Correct	13 ms	23800 KB	Output is correct
16	Correct	12 ms	23748 KB	Output is correct
17	Correct	13 ms	23740 KB	Output is correct
18	Correct	13 ms	23764 KB	Output is correct
19	Correct	194 ms	29820 KB	Output is correct
20	Correct	175 ms	29816 KB	Output is correct
21	Correct	165 ms	29772 KB	Output is correct
22	Correct	145 ms	29992 KB	Output is correct
23	Correct	88 ms	30072 KB	Output is correct
24	Correct	61 ms	29964 KB	Output is correct
25	Correct	193 ms	34252 KB	Output is correct
26	Correct	122 ms	38584 KB	Output is correct
27	Correct	189 ms	36000 KB	Output is correct
28	Correct	266 ms	53488 KB	Output is correct
29	Correct	310 ms	52004 KB	Output is correct
30	Correct	172 ms	36048 KB	Output is correct
31	Correct	161 ms	36140 KB	Output is correct
32	Correct	216 ms	36048 KB	Output is correct
33	Correct	320 ms	34988 KB	Output is correct
34	Correct	193 ms	34964 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23756 KB	Output is correct
3	Correct	11 ms	23844 KB	Output is correct
4	Correct	13 ms	23824 KB	Output is correct
5	Correct	15 ms	23892 KB	Output is correct
6	Correct	12 ms	23812 KB	Output is correct
7	Correct	13 ms	23764 KB	Output is correct
8	Correct	12 ms	23764 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	13 ms	23808 KB	Output is correct
12	Correct	15 ms	23788 KB	Output is correct
13	Correct	16 ms	23764 KB	Output is correct
14	Correct	14 ms	23740 KB	Output is correct
15	Correct	13 ms	23800 KB	Output is correct
16	Correct	12 ms	23748 KB	Output is correct
17	Correct	13 ms	23740 KB	Output is correct
18	Correct	13 ms	23764 KB	Output is correct
19	Correct	13 ms	23764 KB	Output is correct
20	Correct	13 ms	23764 KB	Output is correct
21	Correct	13 ms	23892 KB	Output is correct
22	Correct	15 ms	27400 KB	Output is correct
23	Correct	15 ms	26836 KB	Output is correct
24	Correct	16 ms	27220 KB	Output is correct
25	Correct	15 ms	27160 KB	Output is correct
26	Correct	15 ms	25208 KB	Output is correct
27	Correct	16 ms	26964 KB	Output is correct
28	Correct	14 ms	24624 KB	Output is correct
29	Correct	15 ms	25052 KB	Output is correct
30	Correct	16 ms	25332 KB	Output is correct
31	Correct	14 ms	26324 KB	Output is correct
32	Correct	14 ms	26580 KB	Output is correct
33	Correct	15 ms	26836 KB	Output is correct
34	Correct	15 ms	26112 KB	Output is correct
35	Correct	14 ms	27052 KB	Output is correct
36	Correct	15 ms	27500 KB	Output is correct
37	Correct	14 ms	26976 KB	Output is correct
38	Correct	14 ms	25812 KB	Output is correct
39	Correct	194 ms	29820 KB	Output is correct
40	Correct	175 ms	29816 KB	Output is correct
41	Correct	165 ms	29772 KB	Output is correct
42	Correct	145 ms	29992 KB	Output is correct
43	Correct	88 ms	30072 KB	Output is correct
44	Correct	61 ms	29964 KB	Output is correct
45	Correct	193 ms	34252 KB	Output is correct
46	Correct	122 ms	38584 KB	Output is correct
47	Correct	189 ms	36000 KB	Output is correct
48	Correct	266 ms	53488 KB	Output is correct
49	Correct	310 ms	52004 KB	Output is correct
50	Correct	172 ms	36048 KB	Output is correct
51	Correct	161 ms	36140 KB	Output is correct
52	Correct	216 ms	36048 KB	Output is correct
53	Correct	320 ms	34988 KB	Output is correct
54	Correct	193 ms	34964 KB	Output is correct
55	Correct	24 ms	24344 KB	Output is correct
56	Correct	22 ms	24368 KB	Output is correct
57	Correct	107 ms	30060 KB	Output is correct
58	Correct	44 ms	30104 KB	Output is correct
59	Correct	115 ms	40776 KB	Output is correct
60	Correct	644 ms	59448 KB	Output is correct
61	Correct	191 ms	39120 KB	Output is correct
62	Correct	247 ms	42988 KB	Output is correct
63	Correct	317 ms	42980 KB	Output is correct
64	Correct	666 ms	41304 KB	Output is correct
65	Correct	234 ms	39984 KB	Output is correct
66	Correct	489 ms	56136 KB	Output is correct
67	Correct	142 ms	43608 KB	Output is correct
68	Correct	264 ms	43668 KB	Output is correct
69	Correct	272 ms	43732 KB	Output is correct
70	Correct	261 ms	43044 KB	Output is correct

답안 #543173

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