제출 #1140494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140494		Sang	경주 (Race) (IOI11_race)	C++20	0 / 100	329 ms	327680 KiB

race

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int ans = 1e9, sz[N], block[N], best[N], k;
vector<ii> G[N];

int get_subtree_size(int u, int par = 0){
    sz[u] = 1;
    for (ii &v :  G[u]){
        if (block[v.fi] || v.fi == par) continue;
        sz[u] += get_subtree_size(v.fi, u);
    }
    return sz[u];
}

int get_centroid(int u, int sub_sz, int par = 0){
    for (ii &v : G[u]){
        if (v.fi == par || block[v.fi]) continue;
        if (sz[v.fi] * 2 > sub_sz) return get_centroid(v.fi, sub_sz, u);
    }
    return u;
}

vector<ii> all, sub;

void dfs(int u, int h, int dist, int par = 0){
    if (dist > k) return;
    sub.pb({dist, h});
    all.pb({dist, h});
    ans = min(ans, h + best[k - dist]);
    for (ii & v: G[u]){
        if (v.fi == par || block[v.fi]) continue;
        dfs(v.fi, h + 1, dist + v.se, u);
    }
}

void Centroid(int u){
    int centroid = get_centroid(u, get_subtree_size(u));
    block[centroid] = 1;
    best[0] = 0;
    for (ii & v: G[centroid]){
        dfs(v.fi, 1, v.se, u);
        for (ii &x : sub){
            best[x.fi] = min(best[x.fi], x.se);
        }
        sub.clear();
    }
    for (ii &x : all) best[x.fi] = 1e9;
    all.clear();
    for (ii &x : G[centroid]){
        Centroid(x.fi);
    }

}

int best_path(int N, int K, int H[][2], int L[])
{
    FOR (i, 1, N) best[i] = 1e9;
    k = K;
    FOR (i, 0, N - 2){
        int u = H[i][0] + 1, v = H[i][1] + 1, w = L[i];
        G[u].pb({v, w});
        G[v].pb({u, w});
    }
    Centroid(1);
    return (ans == 1e9 ? -1 : ans);
}

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