Submission #1079027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079027		coolboy19521	Race (IOI11_race)	C++17	100 / 100	2630 ms	242408 KiB

race

#include "race.h"
#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int sz = 2e5 + 10;

vector<pair<int,int>> aj[sz];
map<ll,int> mc[sz], ban;
int ts[sz], k, r;

int uk(int v, int p = -1) {
    ts[v] = 1;
    for (auto& [u, _] : aj[v]) if (u != p)
        ts[v] += uk(u, v);
    return ts[v];
}

int fC(int v, int p = -1) {
    for (auto& [u, _] : aj[v])
        if (u != p && !ban[u])
        if (ts[u] > ts[v] / 2) {
            ts[v] -= ts[u];
            ts[u] += ts[v];
            return fC(u, v);
        }
    return v;
}

void marj(int v, int u) {
    for (auto& [tr, mn] : mc[u])
        if (mc[v].find(tr) != end(mc[v]))
            mc[v][tr] = min(mc[v][tr], mn);
        else mc[v][tr] = mn;
    mc[u].clear();
}

void dfs(int v, int p, int l, int d = 1) {
    mc[v][l] = d;
    for (auto& [u, w] : aj[v])
        if (u != p && !ban[u]) {
            dfs(u, v, l + w, d + 1);
            if (mc[v].size() < mc[u].size())
                mc[v].swap(mc[u]);
            marj(v, u);
        }
}

void cD(int v) {
    v = fC(v);
    mc[v].clear();
    for (auto& [u, w] : aj[v]) if (!ban[u]) {
        dfs(u, v, w);
        if (mc[v].size() < mc[u].size())
            mc[v].swap(mc[u]);
        for (auto& [tr, mn] : mc[u])
            if (mc[v].find(k - tr) != end(mc[v]))
                r = min(r, mn + mc[v][k - tr]);
        marj(v, u);
    }
    if (mc[v].find(k) != end(mc[v]))
        r = min(r, mc[v][k]);
    ban[v] = 1;
    for (auto& [u, _] : aj[v])
        if (!ban[u]) cD(u);
}

int best_path(int N, int K, int H[][2], int L[]) {
    if (1 == N) {
        if (0 == K) return 0;
        else return -1;
    }
    for (int i = 0; i < N - 1; i ++) {
        int a = H[i][0], b = H[i][1];
        aj[a].emplace_back(b, L[i]);
        aj[b].emplace_back(a, L[i]);
    }
    r = N, k = K;
    uk(0);
    cD(0);
    return r < N ? r : -1;
}

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