Submission #104396

#	Time	Username	Problem	Language	Result	Execution time	Memory
104396		dfistric	Race (IOI11_race)	C++14	21 / 100	3094 ms	13532 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;

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;

    int ma = si - sub[x];
    for (auto tr : ve[x]) {
        int y = tr.first;
        if (bio[y] >= cnt) continue;
        int t = find_centroid(y);
        if (t != -1) return y;

        ma = max(ma, sub[y]);
    }

    if (ma <= si / 2) return x;
    return -1;
}

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: 0 / 22
• Subtask 4: 0 / 57