제출 #726528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726528		hoainiem	경주 (Race) (IOI11_race)	C++14	100 / 100	542 ms	32280 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define nmax 200008
#define kmax 1000008
const int inf = 1e9;
using namespace std;
typedef pair<int, int> pii;
int n, k, lim, ans = inf, sz[nmax], f[kmax];
bool kt[nmax];
vector<pii>l[nmax];
int dfs(int x, int pre){
    sz[x] = 1;
    for (pii it : l[x]){
        if (it.fi == pre || kt[it.fi])
            continue;
        sz[x] += dfs(it.fi, x);
    }
    return sz[x];
}
int centroid(int rt, int x, int pre){
    for (pii it : l[x]){
        if (it.fi == pre || kt[it.fi])
            continue;
        if (sz[it.fi] * 2 > sz[rt])
            return centroid(rt, it.fi, x);
    }
    return x;
}
void calc(int x, int pre, int dis, int d, int flag){
    if (dis > k)
        return;
    switch(flag){
        case 0:
            ans = min(ans, f[k - dis] + d);
            break;
        case 1:
            f[dis] = min(f[dis], d);
            break;
        default:
            f[dis] = inf;
            break;
    }
    for (pii it : l[x]){
        if (it.fi == pre || kt[it.fi])
            continue;
        calc(it.fi, x, dis + it.se, d + 1, flag);
    }
}
void centroid(int x){
    dfs(x, x);
    x = centroid(x, x, x);
    f[0] = 0;
    for (pii it : l[x])
        if (!kt[it.fi]){
            calc(it.fi, x, it.se, 1, 0);
            calc(it.fi, x, it.se, 1, 1);
        }
    for (pii it : l[x])
        if (!kt[it.fi])
            calc(it.fi, x, it.se, 1, 2);
    kt[x] = 1;
    f[0] = inf;
    for (pii it : l[x])
        if (!kt[it.fi])
            centroid(it.fi);
}
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], w = L[i];
        l[u].push_back({v, w});
        l[v].push_back({u, w});
    }
    memset(kt, false, sizeof(kt));
    fill(f, f + k + 1, inf);
    centroid(1);
    if (ans >= n)
        ans = -1;
    return ans;
}

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