Submission #98946

#	Time	Username	Problem	Language	Result	Execution time	Memory
98946		Hideo	Race (IOI11_race)	C++14	21 / 100	3046 ms	14684 KiB

race

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

using namespace std;

#define mk make_pair
#define pb push_back
#define sc second
#define fr first
#define pii pair < int, int >
#define vii vector < pii >

const int MAXN = 2e5 + 7;
const int MAXK = 1e6 + 7;
const int INF = 1e9 + 7;

int ans = INF, k;
int st[MAXK], h[MAXN], del[MAXN];

vii g[MAXN];

void dfs (int v, int p = -1){
    h[v] = 1;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            dfs(to.fr, v);
    if (p != -1)
        h[p] += h[v];
}

int centroid (int v){
    dfs(v);
    bool ok = true;
    int c = v, pr = 0;
    while (ok){
        ok = false;
        for (pii to : g[c]){
            if (to.fr != pr && !del[to.fr] && h[to.fr] * 2 >= h[v]){
                pr = c;
                c = to.fr;
                ok = true;
                break;
            }
        }
    }
    return c;
}

void findAns (int v, int p, int l, int d = 1){
    if (k > l && st[k - l])
        ans = min(ans, d + st[k - l]);
    if (k == l)
        ans = min(ans, d);
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            findAns (to.fr, v, l + to.sc, d + 1);
}

void upd (int v, int p, int l, int d = 1){
    if (k > l && st[l])
        st[l] = min(st[l], d);
    else if (k > l)
        st[l] = d;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            upd(to.fr, v, l + to.sc, d + 1);
}

void calc (int v = 0){
    v = centroid(v);
    del[v] = 1;
    memset(st, 0, sizeof(st));
    for (pii to : g[v]){
        if (!del[to.fr]){
            findAns(to.fr, v, to.sc);
            upd(to.fr, v, to.sc);
        }
    }
    for (pii to : g[v])
        if (!del[to.fr])
            calc (to.fr);
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int i = 0; i < N - 1; i++){
        g[H[i][0]].pb(mk(H[i][1], L[i]));
        g[H[i][1]].pb(mk(H[i][0], L[i]));
    }
    calc();
    if (ans == INF)
        return -1;
    return ans;
}

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