제출 #1262613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262613		denilb	경주 (Race) (IOI11_race)	C++20	100 / 100	430 ms	31668 KiB

race

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

const int inf = 1e9;
const int maxn = 200005;
const int maxk = 1000005;

int sz[maxn], rem[maxn], length[maxk];
vector<pair<int,int>> adj[maxn];
int n, k, ans;

int get_sz(int v, int p=-1){
    sz[v] = 1;
    for(auto [u, w]: adj[v]){
        if(u == p || rem[u]) continue;
        sz[v] += get_sz(u, v);
    }
    return sz[v];
}

int get_centroid(int tsz, int v, int p=-1){
    for(auto [u, w]: adj[v]){
        if(u == p || rem[u]) continue;
        if(2 * sz[u] > tsz)
            return get_centroid(tsz, u, v);
    }
    return v;
}

void dfs(int v, int p, int w, int d, int filling){
    if(w > k) return;
    if(filling == 1) length[w] = min(length[w], d);
    if(filling == -1) length[w] = inf;
    if(filling == 0) ans = min(ans, length[k-w] + d);
    for(auto [u, nw]: adj[v]){
        if(u == p || rem[u]) continue;
        dfs(u, v, w+nw, d+1, filling);
    }
}

void centroid_decomp(int v){
    int centroid = get_centroid(get_sz(v), v);
    rem[centroid] = true;
    for(auto [u, w]: adj[centroid]){
        if(rem[u]) continue;
        dfs(u, centroid, w, 1, 0);
        dfs(u, centroid, w, 1, 1);
    }
    for(auto [u, w]: adj[centroid]){
        if(rem[u]) continue;
        dfs(u, centroid, w, 1, -1);
    }
    for(auto [u, w]: adj[centroid]){
        if(rem[u]) continue;
        centroid_decomp(u);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n=N, k=K;
    for(int i=0; i<n-1; i++){
        int u=H[i][0], v=H[i][1];
        adj[u].push_back(make_pair(v, L[i]));
        adj[v].push_back(make_pair(u, L[i]));
    }
    fill(length+1, length+maxk, inf);
    length[0] = 0;
    ans = inf;
    centroid_decomp(0);
    if(ans == inf) ans = -1;
    return ans;
}

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