Submission #176876

#	Time	Username	Problem	Language	Result	Execution time	Memory
176876		tri	Race (IOI11_race)	C++14	100 / 100	2860 ms	47232 KiB

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57