Submission #990370

#	Time	Username	Problem	Language	Result	Execution time	Memory
990370		stdfloat	Race (IOI11_race)	C++17	100 / 100	735 ms	50260 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

int k, mn = INT_MAX;

vector<int> sz;

map<int, int> m;

vector<bool> vis;

vector<vector<pii>> v, E;

int dfs_sz(int x, int p = -1) {
    sz[x] = 1;
    for (auto [i, w] : E[x]) {
        if (i != p && !vis[i]) sz[x] += dfs_sz(i, x);
    }

    return sz[x];
}

int ctrd(int x, int p, int n) {
    for (auto [i, w] : E[x]) {
        if (i != p && !vis[i] && sz[i] > (n >> 1)) return ctrd(i, x, n);
    }

    return x;
}

void dfs(int x, int p, int d1, int d2) {
    for (auto [i, w] : E[x]) {
        if (i != p && !vis[i] && w <= k - d2) {
            m[d2 + w] = min((m[d2 + w] ? m[d2 + w] : INT_MAX), d1 + 1);
            dfs(i, x, d1 + 1, d2 + w);
        }
    }
}

void f(int x, int p = -1) {
    int n = dfs_sz(x), c = ctrd(x, p, n);

    vis[c] = true;

    map<int, int> M; M[0] = 0;
    for (auto [i, w] : E[c]) {
        if (vis[i]) continue;

        m = {{w, 1}};
        dfs(i, c, 1, w);

        for (auto i : m) {
            if (M.find(k - i.ff) != M.end()) mn = min(mn, M[k - i.ff] + i.ss);
        }
        for (auto i : m)
            M[i.ff] = min((M[i.ff] ? M[i.ff] : INT_MAX), i.ss);
    }

    for (auto [i, w] : E[c])
        if (!vis[i]) f(i, c);
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
    E.assign(N, {});
    for (int i = 0; i < N - 1; i++) {
        E[H[i][0]].push_back({H[i][1], L[i]});
        E[H[i][1]].push_back({H[i][0], L[i]});
    }

    sz.assign(N, 0);
    vis.assign(N, false);
    f(0);

    return (mn == INT_MAX ? -1 : mn);
}

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