Submission #855211

#	Time	Username	Problem	Language	Result	Execution time	Memory
855211		thisistotallymyusername	Race (IOI11_race)	C++14	100 / 100	294 ms	65580 KiB

race

/*
dsu: (ds[y] - ds[x]) + (ds[z] - ds[x]) = k
     ds[z] = k + 2 ds[x] - ds[y];

     # edges = (dep[y] - dep[x]) + (dep[z] - dep[x])
 */

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

#define F first
#define S second

const int N = 200010, INF = 0x3f3f3f3f;

int res = INF;
int h[2 * N], e[2 * N], ne[2 * N], w[2 * N], idx;
map<int, int> dep[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa, int dist, int depth, int k) {
    dep[u][dist] = depth;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) {
            continue;
        }
        dfs(j, u, dist + w[i], depth + 1, k);
        if (dep[u].size() < dep[j].size()) {
            swap(dep[u], dep[j]);
        }
        for (auto t : dep[j]) {
            int ds = k + 2 * dist - t.F;
            if (ds >= 0 && dep[u].count(ds) > 0) {
                res = min(res, dep[u][ds] + dep[j][t.F] - 2 * depth);
            }
        }
        for (auto t : dep[j]) {
            if (dep[u][t.F]) dep[u][t.F] = min(dep[u][t.F], t.S);
            else dep[u][t.F] = t.S;
        }
        dep[j].clear();
    }
}


int best_path(int N, int K, int H[][2], int L[]) {
    memset(h, -1, sizeof h);
    for (int i = 0; i < N - 1; i++) {
        add(H[i][0] + 1, H[i][1] + 1, L[i]);
        add(H[i][1] + 1, H[i][0] + 1, L[i]);
    }
    dfs(1, -1, 0, 1, K);
    return (res == INF ? -1 : res);
}

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