Submission #1214663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214663		shelby70	Race (IOI11_race)	C++20	0 / 100	3 ms	6472 KiB

race

#ifndef LOCAL
#include <bits/stdc++.h>
#define debug(...)
#endif

using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5, H = 18, INF = 1e9;
int arr[N], sub[N], cth[N], ctp[N], mn[M], ans = INF, n, k;
vector<pair<int, int> > g[N];

void dfs_siz(int u, int p) {
    sub[u] = 1;
    for (auto &[v,w]: g[u]) if (!cth[v] && v ^ p) dfs_siz(v, u), sub[u] += sub[v];
}

int fc(int u, int p, int lim) {
    for (auto &[v,w]: g[u]) if (!cth[v] && v ^ p && sub[v] > lim) return fc(v, u, lim);
    return u;
}

void dfs_calc(int u, int p, int len, int d, int mark) {
    if (len > k) return;
    if (mark == 0) {
        int need = k - len;
        ans = min(ans, d + mn[need]);
    }
    else if (mark == 1) mn[len] = min(mn[len], d);
    else mn[len] = INF;
    for (auto [v,w]: g[u]) if (!cth[v] && p ^ v) dfs_calc(v, u, len + w, d + 1, mark);
}

void decompose(int u, int p, int h) {
    dfs_siz(u, 0);
    u = fc(u, 0, sub[u] >> 1);
    cth[u] = h, ctp[u] = p;
    for (auto &[v,w]: g[u])
        if (!cth[v]) {
            dfs_calc(v, u, w, 1, false);
            dfs_calc(v, u, w, 1, true);
        }
    for (auto &[v,w]: g[u]) if (!cth[v]) dfs_calc(v, u, w, 1, 2);
    for (auto &[v,w]: g[u]) if (!cth[v]) decompose(v, u, h + 1);
}

int best_path(int _n, int _k, int H[][2], int L[]) {
    n = _n, k = _k;
    fill_n(mn, M, INF);
    for (int i = 0; i < n - 1; ++i) {
        int u = H[i][0], v = H[i][1], w = L[i];
        u++, v++;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    decompose(1, 0, 1);
    return ans == INF ? -1 : ans;
}

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