Submission #855210

#	Time	Username	Problem	Language	Result	Execution time	Memory
855210		thisistotallymyusername	Race (IOI11_race)	C++14	0 / 100	245 ms	262144 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;

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);
        for (auto t : dep[j]) {
            int ds = k + 2 * dist - t.first;
            if (ds >= 0 && dep[u].count(ds) > 0) {
                res = min(res, dep[u][ds] + dep[j][t.first] - 2 * depth);
            }
        }
        for (auto t : dep[j]) {
            if (dep[u][t.first]) dep[u][t.first] = min(dep[u][t.first], t.second);
            else dep[u][t.first] = t.second;
        }
    }
}


int best_path(int n, int k, int he[][2], int l[]) {
    for (int i = 0; i < n - 1; i++) {
        add(he[i][0] + 1, he[i][1] + 1, l[i]), add(he[i][1] + 1, he[i][0] + 1, l[i]);

    }
    dfs(1, -1, 0, 1, k);
    return (res == INF ? -1 : res);
}

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