Submission #1177846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177846		MinhKien	Race (IOI11_race)	C++20	100 / 100	281 ms	28976 KiB

race

#include <iostream>
#include <vector>

using namespace std;

#define ii pair <int, int>
#define fi first
#define se second
const int N = 2e5 + 10;
const int M = 1e6 + 10;

int n, k, x, y, w;
vector <ii> v[N];
int sz[N], dis[M];
bool solved[N];

int calc_size(int s, int p = -1) {
    sz[s] = 1;
    for (ii z: v[s]) {
        if (z.fi == p || solved[z.fi]) continue;
        sz[s] += calc_size(z.fi, s);
    }
    return sz[s];
}

int FindCentroid(int s, int Size, int p = -1) {
    for (ii z: v[s]) {
        if (z.fi == p || solved[z.fi]) continue;
        if (sz[z.fi] > Size) return FindCentroid(z.fi, Size, s);
    }
    return s;
}

int ans = 1e9, mx;
void run(int s, int p, int depth, int len, bool filling) {
    if (len > k) return;

    mx = max(mx, len);
    if (filling) {
        if (dis[len] == 0) dis[len] = depth;
        else dis[len] = min(dis[len], depth);
    } else {
        if (dis[k - len] != 0) ans = min(ans, dis[k - len] + depth);
        if (len == k) ans = min(ans, depth);
    }

    for (ii z: v[s]) {
        if (z.fi == p || solved[z.fi]) continue;
        run(z.fi, s, depth + 1, len + z.se, filling);
    }
}

void CentroidDecomp(int s = 1) {
    int cen = FindCentroid(s, calc_size(s) >> 1);
    solved[cen] = true;

    mx = 0;
    for (ii z: v[cen]) {
        if (solved[z.fi]) continue;
        run(z.fi, cen, 1, z.se, false);
        run(z.fi, cen, 1, z.se, true);
    }
    fill_n(dis, mx + 1, 0);

    for (ii z: v[cen]) {
        if (solved[z.fi]) continue;
        CentroidDecomp(z.fi);
    }
}

int best_path(int NN, int KK, int H[][2], int L[]) {
    n = NN;
    k = KK;
    for (int i = 0; i < n - 1; ++i) {
        x = H[i][0], y = H[i][1], w = L[i];
        ++x, ++y;
        v[x].push_back(ii(y, w));
        v[y].push_back(ii(x, w));
    }

    CentroidDecomp();
    if (ans == 1e9) ans = -1;

    return ans;
}

//「名前だけで、どうやって君のことを覚えていられるの？」
//「結局、君の名前さえちゃんと分からないんだ？」

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57