Submission #337091

#	Time	Username	Problem	Language	Result	Execution time	Memory
337091		Joshc	Race (IOI11_race)	C++11	100 / 100	542 ms	35596 KiB

race

#include "race.h"
#include <vector>
using namespace std;

#define f first
#define s second
#define pii pair<int, int>

const int MAX_N = 200001;
vector<pii> edges[MAX_N], lengths;
vector<int> cur;
int k, num[MAX_N], best[1000001], ans = 1e9;
bool removed[MAX_N];

int dfs(int v, int p) {
    num[v] = 1;
    for (pii u : edges[v]) {
        if (u.f != p && !removed[u.f]) num[v] += dfs(u.f, v);
    }
    return num[v];
}

int centroid(int v, int p, int n) {
    for (pii u : edges[v]) {
        if (u.f != p && !removed[u.f] && num[u.f]>n/2) return centroid(u.f, v, n);
    }
    return v;
}

void getlengths(int v, int p, int c, int d) {
    if (c > k) return;
    lengths.emplace_back(c, d);
    for (pii u : edges[v]) {
        if (u.f != p && !removed[u.f]) getlengths(u.f, v, c+u.s, d+1);
    }
}

void solve(int v) {
    removed[v] = true;
    for (pii u : edges[v]) {
        if (!removed[u.f]) {
            lengths.clear();
            getlengths(u.f, v, u.s, 1);
            for (pii length : lengths) {
                if (length.f == k) ans = min(ans, length.s);
                ans = min(ans, length.s+best[k-length.f]);
                cur.push_back(length.f);
            }
            for (pii length : lengths) best[length.f] = min(best[length.f], length.s);
        }
    }
    for (int i : cur) best[i] = 1e9;
    cur.clear();
    for (pii u : edges[v]) {
        if (!removed[u.f]) solve(centroid(u.f, u.f, dfs(u.f, u.f)));
    }
}

int best_path(int n, int K, int H[][2], int L[]) {
    k = K;
    for (int i=0; i<n-1; i++) {
        edges[H[i][0]].emplace_back(H[i][1], L[i]);
        edges[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    for (int i=0; i<1000001; i++) best[i] = 1e9;
    dfs(0, 0);
    solve(centroid(0, 0, n));
    return ans==1e9 ? -1 : ans;
}

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