Submission #16998

#	Time	Username	Problem	Language	Result	Execution time	Memory
16998		murat	Race (IOI11_race)	C++98	100 / 100	582 ms	72804 KiB

race

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

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

using namespace std;

#define pii pair < int ,int > 

const int N = 1e6 + 5;
const int inf = 1e9 + 7;

int ans = inf;
int k, H[N], h[N], n, m, x, y, t, S, sum[N];
vector< pii > v[N], g[N];

int prep(int node, int root) {
    sum[node] = 1;
    foreach(it, v[node])
        if(!h[it->st] && it->st != root)
            sum[node] += prep(it->st, node);
    return sum[node];
}

int find(int node, int root) {
    foreach(it, v[node])
        if(!h[it->st] && it->st != root && sum[it->st] > S)
            return find(it->st, node);
    return node;
}

void dfs(int node, int root, int dist, int S, int t) {
    if(dist > k) return ;
    g[S].pb(mp(dist, t));
    foreach(it, v[node])
        if(it->st != root && !h[it->st])
            dfs(it->st, node, it->nd + dist, S, t + 1);
}

void solve(int node) {

    prep(node, 0); S = sum[node] >> 1;

    node = find(node, 0);

    h[node] = 1;

    S = 0;

    foreach(it, v[node]) {
        if(!h[it->st]) {
            g[++S].clear();
            dfs(it->st, node, it->nd, S, 1);
        }
    }

    H[0] = 0;

    FOR(i, 1, S) {
        foreach(it, g[i])
            if(it->st <= k)
                ans = min(H[k-it->st] + it->nd, ans);
        foreach(it, g[i])
            if(it->st <= k)
                 H[it->st] = min(H[it->st], it->nd);
    }

    H[0] = inf;

    FOR(i, 1, S)
        foreach(it, g[i])
            if(it->st <= k)
                H[it->st] = inf;

    foreach(it, v[node])
        if(!h[it->st])
            solve(it->st);

}

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 x = H[i][0],
            y = H[i][1];
        v[x].pb(mp(y, L[i]));
        v[y].pb(mp(x, L[i]));
    }

    memset(::H, 10, sizeof ::H);

    ans = inf;

    solve(1);

    if(ans > n) ans = -1;

    return ans;
}

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