Submission #1221544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221544		nguyn	경주 (Race) (IOI11_race)	C++20	100 / 100	400 ms	34108 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int maxN = 2e5 + 5;
const int maxW = 1e6 + 5;
const int inf = 1e9;

int n, sz[maxN], k;
vector<pii> g[maxN];
int edges[maxN][2], len[maxN];
int h[maxN], d[maxN];
int best[maxW];
int del[maxN];
int res = inf;

void count_child(int u, int p) {
    sz[u] = 1;
    for (pii it : g[u]) {
        int v = it.F;
        int w = it.S;
        if (v == p || del[v]) continue;
        count_child(v, u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int p, int n) {
    for (pii it : g[u]) {
        int v = it.F;
        int w = it.S;
        if (v == p || del[v]) continue;
        if (sz[v] > n / 2) return find_centroid(v, u, n);
    }
    return u;
}

void update(int u, int p, bool sta) {
    if (sta == 0) {
        if (d[u] == k) res = min(res, h[u]);
        if (d[u] < k) {
            if (best[k - d[u]] != 0) res = min(res, best[k - d[u]] + h[u]);
        }
    }
    else {
        if (d[u] <= k) {
            if (best[d[u]] == 0) best[d[u]] = h[u];
            else best[d[u]] = min(best[d[u]], h[u]);
        }
    }
    for (pii it : g[u]) {
        int v = it.F;
        int w = it.S;
        if (v == p || del[v]) continue;
        h[v] = h[u] + 1;
        d[v] = d[u] + w;
        update(v, u, sta);
    }
}

void delAns(int u, int p) {
    if (d[u] <= k) best[d[u]] = 0;
    for (pii it : g[u]) {
        int v = it.F;
        int w = it.S;
        if (v == p || del[v]) continue;
        delAns(v, u);
    }
}

void solve(int u) {
    count_child(u, 0);

    int n = sz[u];
    int root = find_centroid(u, 0, n);

    del[root] = 1;

    for (pii it : g[root]) {
        int v = it.F;
        int w = it.S;
        if (del[v]) continue;
        h[v] = 1;
        d[v] = w;
        update(v, root, 0);
        update(v, root, 1);
    }
    d[root] = 0;
    delAns(root, 0);

    for (pii it : g[root]) {
        int v = it.F;
        int w = it.S;
        if (del[v]) continue;
        solve(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for (int i = 0; i < n - 1; i++) {
        H[i][0]++;
        H[i][1]++;
        g[H[i][0]].pb({H[i][1], L[i]});
        g[H[i][1]].pb({H[i][0], L[i]});
    }
    solve(1);
    if (res == inf) return -1;
    return res;
}


//signed main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cin >> n >> k;
//    for (int i = 0; i < n - 1; i++) {
//        cin >> edges[i][0] >> edges[i][1] >> len[i];
//    }
//    cout << best_path(n, k, edges, len);
//}

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