제출 #104397

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

race

#include <bits/stdc++.h>
#include "race.h"

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

const int MAXN = 200100;
vector <pair <int, int> > ve[MAXN];
int sub[MAXN];
int bio[MAXN], cnt;
int n, k;
int out_len = MAXN;
int len[5 * MAXN];
int date[5 * MAXN];
int num;

int tmp;

void rek1(int x, int l, int di) {
    if (l > k) return;
    if (k >= l && date[k - l] == num) {
        out_len = min(out_len, di + len[k - l]);
    }

    bio[x] = cnt;
    for (auto tr : ve[x]) {
        int y = tr.first, d = tr.second;
        if (bio[y] >= cnt) continue;
        rek1(y, l + d, di + 1);
    }

    return;
}

void rek2(int x, int l, int di) {
    if (l > k) return;
    if (date[l] < num) {
        date[l] = num;
        len[l] = 1e9;
    }
    len[l] = min(len[l], di);

    bio[x] = cnt;
    for (auto tr : ve[x]) {
        int y = tr.first, d = tr.second;
        if (bio[y] >= cnt) continue;
        rek2(y, l + d, di + 1);
    }

    return;
}

void solve(int x) {
    bio[x] = 1e9;

    num++;
    cnt++;
    date[0] = num, len[0] = 0;
    for (auto tr : ve[x]) {
        int y = tr.first, d = tr.second;
        if (bio[y] >= cnt) continue;
        rek1(y, d, 1);
        cnt++;
        rek2(y, d, 1);
        cnt++;
    }

    return;
}

int si;
void dfs(int x) {
    si++;
    bio[x] = cnt;
    sub[x] = 1;
    for (auto tr : ve[x]) {
        int y = tr.first;
        if (bio[y] >= cnt) continue;
        dfs(y);
        sub[x] += sub[y];
    }
    return;
}

int find_centroid(int x) {
    bio[x] = cnt;

    for (auto tr : ve[x]) {
        int y = tr.first;
        if (bio[y] >= cnt) continue;
        if (sub[y] > si / 2) return find_centroid(y);
    }

    return x;
}

void decompose(int x) {
    cnt++, si = 0;
    dfs(x);

    cnt++;
    int c = find_centroid(x);

    solve(c);

    for (auto tr : ve[c]) {
        int y = tr.first;
        if (bio[y] != 1e9) decompose(y);
    }
    return;
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;

    REP(i, n) {
        int a = H[i][0], b = H[i][1], c = L[i];
        ve[a].push_back({b, c});
        ve[b].push_back({a, c});
    }

    decompose(0);

    if (out_len == MAXN) return -1;
    return out_len;
}

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