답안 #176876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
176876	2020-01-08T05:26:07 Z	tri	경주 (Race) (IOI11_race)	C++14	100 / 100	2860 ms	47232 KB

race

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, ll> pil;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

int N, K;

const int MAXN = 2e5 + 100;

vector<pl> aL[MAXN];

int ctPar[MAXN], vCnt[MAXN], rem[MAXN];

int gSize;

void fCnt(int cV, int pV) {
    vCnt[cV] = 1;
    for (pl aE : aL[cV]) {
        int aV = aE.f;
        if (aV != pV && !rem[aV]) {
            fCnt(aV, cV);
            vCnt[cV] += vCnt[aV];
        }
    }
}

int fCent(int cV, int pV) {
    for (pl aE : aL[cV]) {
        int aV = aE.f;
        if (aV != pV && !rem[aV] && vCnt[aV] > gSize / 2) {
            return fCent(aV, cV);
        }
    }
    return cV;
}

multiset<pl> pPaths;

ll ans = 1e9;

void cPaths(int cV, int pV, ll cD, int eCnt, int mode) {
    if (mode == 1) {
        pPaths.insert({cD, eCnt});
    } else if (mode == -1) {
        pPaths.erase({cD, eCnt});
    } else {
        auto match = pPaths.lower_bound({K - cD, 0});
        pl mPair = *match;
        if (match != pPaths.end() && mPair.f == K - cD) {
            ans = min(ans, eCnt + mPair.s);
        }
    }

    for (pl aE : aL[cV]) {
        int aV = aE.f;
        if (aV != pV && !rem[aV]) {
            cPaths(aV, cV, cD + aE.s, eCnt + 1, mode);
        }
    }
}

void decomp(int root, int cCtPar) {
    fCnt(root, -1);
    gSize = vCnt[root];
    int cent = fCent(root, -1);

    ctPar[cent] = cCtPar;
    rem[cent] = true;

    pPaths.clear();

    cPaths(cent, -1, 0, 0, 1);

    for (pl aE : aL[cent]) {
        int aV = aE.f;

        if (!rem[aV]) {
            cPaths(aV, cent, aE.s, 1, -1);

            cPaths(aV, cent, aE.s, 1, 0);

            cPaths(aV, cent, aE.s, 1, 1);
        }
    }

    for (pl aE : aL[cent]) {
        int aV = aE.f;
        if (!rem[aV]) {
            decomp(aV, cent);
        }
    }
}


int best_path(int iN, int iK, int H[][2], int L[]) {
    N = iN;
    K = iK;

    memset(rem, 0, sizeof(rem));

    for (int i = 0; i < N - 1; i++) {
        aL[H[i][0]].pb({H[i][1], L[i]});
        aL[H[i][1]].pb({H[i][0], L[i]});
    }

    decomp(0, -1);

    if (ans == 1e9) {
        return -1;
    } else {
        return ans;
    }
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5800 KB	Output is correct
3	Correct	7 ms	5880 KB	Output is correct
4	Correct	7 ms	5840 KB	Output is correct
5	Correct	7 ms	5880 KB	Output is correct
6	Correct	7 ms	5800 KB	Output is correct
7	Correct	7 ms	5880 KB	Output is correct
8	Correct	7 ms	5880 KB	Output is correct
9	Correct	7 ms	5880 KB	Output is correct
10	Correct	7 ms	5880 KB	Output is correct
11	Correct	7 ms	5880 KB	Output is correct
12	Correct	7 ms	5852 KB	Output is correct
13	Correct	7 ms	5852 KB	Output is correct
14	Correct	7 ms	5880 KB	Output is correct
15	Correct	7 ms	5880 KB	Output is correct
16	Correct	7 ms	5880 KB	Output is correct
17	Correct	7 ms	5880 KB	Output is correct
18	Correct	7 ms	5880 KB	Output is correct
19	Correct	7 ms	5752 KB	Output is correct
20	Correct	7 ms	5880 KB	Output is correct
21	Correct	10 ms	6008 KB	Output is correct
22	Correct	10 ms	6008 KB	Output is correct
23	Correct	11 ms	6008 KB	Output is correct
24	Correct	10 ms	6008 KB	Output is correct
25	Correct	10 ms	6008 KB	Output is correct
26	Correct	12 ms	5952 KB	Output is correct
27	Correct	9 ms	6008 KB	Output is correct
28	Correct	10 ms	6028 KB	Output is correct
29	Correct	10 ms	5988 KB	Output is correct
30	Correct	10 ms	6040 KB	Output is correct
31	Correct	10 ms	5980 KB	Output is correct
32	Correct	10 ms	6008 KB	Output is correct
33	Correct	10 ms	6008 KB	Output is correct
34	Correct	10 ms	6008 KB	Output is correct
35	Correct	10 ms	6008 KB	Output is correct
36	Correct	10 ms	5976 KB	Output is correct
37	Correct	9 ms	6008 KB	Output is correct
38	Correct	10 ms	6008 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5800 KB	Output is correct
3	Correct	7 ms	5880 KB	Output is correct
4	Correct	7 ms	5840 KB	Output is correct
5	Correct	7 ms	5880 KB	Output is correct
6	Correct	7 ms	5800 KB	Output is correct
7	Correct	7 ms	5880 KB	Output is correct
8	Correct	7 ms	5880 KB	Output is correct
9	Correct	7 ms	5880 KB	Output is correct
10	Correct	7 ms	5880 KB	Output is correct
11	Correct	7 ms	5880 KB	Output is correct
12	Correct	7 ms	5852 KB	Output is correct
13	Correct	7 ms	5852 KB	Output is correct
14	Correct	7 ms	5880 KB	Output is correct
15	Correct	7 ms	5880 KB	Output is correct
16	Correct	7 ms	5880 KB	Output is correct
17	Correct	7 ms	5880 KB	Output is correct
18	Correct	7 ms	5880 KB	Output is correct
19	Correct	1039 ms	20548 KB	Output is correct
20	Correct	1046 ms	20532 KB	Output is correct
21	Correct	959 ms	20536 KB	Output is correct
22	Correct	844 ms	20612 KB	Output is correct
23	Correct	1236 ms	21000 KB	Output is correct
24	Correct	521 ms	20216 KB	Output is correct
25	Correct	994 ms	25600 KB	Output is correct
26	Correct	601 ms	26272 KB	Output is correct
27	Correct	896 ms	35912 KB	Output is correct
28	Correct	2412 ms	47232 KB	Output is correct
29	Correct	2470 ms	46340 KB	Output is correct
30	Correct	888 ms	35860 KB	Output is correct
31	Correct	891 ms	35856 KB	Output is correct
32	Correct	1057 ms	35928 KB	Output is correct
33	Correct	1787 ms	34708 KB	Output is correct
34	Correct	2455 ms	35524 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5800 KB	Output is correct
3	Correct	7 ms	5880 KB	Output is correct
4	Correct	7 ms	5840 KB	Output is correct
5	Correct	7 ms	5880 KB	Output is correct
6	Correct	7 ms	5800 KB	Output is correct
7	Correct	7 ms	5880 KB	Output is correct
8	Correct	7 ms	5880 KB	Output is correct
9	Correct	7 ms	5880 KB	Output is correct
10	Correct	7 ms	5880 KB	Output is correct
11	Correct	7 ms	5880 KB	Output is correct
12	Correct	7 ms	5852 KB	Output is correct
13	Correct	7 ms	5852 KB	Output is correct
14	Correct	7 ms	5880 KB	Output is correct
15	Correct	7 ms	5880 KB	Output is correct
16	Correct	7 ms	5880 KB	Output is correct
17	Correct	7 ms	5880 KB	Output is correct
18	Correct	7 ms	5880 KB	Output is correct
19	Correct	7 ms	5752 KB	Output is correct
20	Correct	7 ms	5880 KB	Output is correct
21	Correct	10 ms	6008 KB	Output is correct
22	Correct	10 ms	6008 KB	Output is correct
23	Correct	11 ms	6008 KB	Output is correct
24	Correct	10 ms	6008 KB	Output is correct
25	Correct	10 ms	6008 KB	Output is correct
26	Correct	12 ms	5952 KB	Output is correct
27	Correct	9 ms	6008 KB	Output is correct
28	Correct	10 ms	6028 KB	Output is correct
29	Correct	10 ms	5988 KB	Output is correct
30	Correct	10 ms	6040 KB	Output is correct
31	Correct	10 ms	5980 KB	Output is correct
32	Correct	10 ms	6008 KB	Output is correct
33	Correct	10 ms	6008 KB	Output is correct
34	Correct	10 ms	6008 KB	Output is correct
35	Correct	10 ms	6008 KB	Output is correct
36	Correct	10 ms	5976 KB	Output is correct
37	Correct	9 ms	6008 KB	Output is correct
38	Correct	10 ms	6008 KB	Output is correct
39	Correct	1039 ms	20548 KB	Output is correct
40	Correct	1046 ms	20532 KB	Output is correct
41	Correct	959 ms	20536 KB	Output is correct
42	Correct	844 ms	20612 KB	Output is correct
43	Correct	1236 ms	21000 KB	Output is correct
44	Correct	521 ms	20216 KB	Output is correct
45	Correct	994 ms	25600 KB	Output is correct
46	Correct	601 ms	26272 KB	Output is correct
47	Correct	896 ms	35912 KB	Output is correct
48	Correct	2412 ms	47232 KB	Output is correct
49	Correct	2470 ms	46340 KB	Output is correct
50	Correct	888 ms	35860 KB	Output is correct
51	Correct	891 ms	35856 KB	Output is correct
52	Correct	1057 ms	35928 KB	Output is correct
53	Correct	1787 ms	34708 KB	Output is correct
54	Correct	2455 ms	35524 KB	Output is correct
55	Correct	57 ms	7340 KB	Output is correct
56	Correct	59 ms	7316 KB	Output is correct
57	Correct	864 ms	20900 KB	Output is correct
58	Correct	138 ms	19860 KB	Output is correct
59	Correct	745 ms	26360 KB	Output is correct
60	Correct	2425 ms	46508 KB	Output is correct
61	Correct	936 ms	36052 KB	Output is correct
62	Correct	888 ms	35916 KB	Output is correct
63	Correct	1060 ms	35904 KB	Output is correct
64	Correct	2860 ms	35960 KB	Output is correct
65	Correct	2379 ms	36448 KB	Output is correct
66	Correct	2442 ms	45796 KB	Output is correct
67	Correct	405 ms	35184 KB	Output is correct
68	Correct	1232 ms	35876 KB	Output is correct
69	Correct	1223 ms	36092 KB	Output is correct
70	Correct	1160 ms	34704 KB	Output is correct

답안 #176876

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