Submission #1228484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228484		stdfloat	Race (IOI11_race)	C++17	100 / 100	272 ms	88980 KiB

race

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

using ll = long long;

const int N = (int)2e5 + 5;

int K, ans;

vector<int> D, sz;

vector<ll> S;

vector<map<ll, int>*> m;

vector<vector<pair<int, int>>> E;

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

    return sz[x];
}

void dfs(int x, int p = -1) {
    int y = -1;
    for (auto [i, w] : E[x]) {
        if (i != p && (!~y || sz[y] < sz[i])) y = i;
    }

    if (~y) {
        dfs(y, x);
        m[x] = m[y];
    }
    else m[x] = new map<ll, int> ();

    (*m[x])[S[x]] = D[x];

    if (m[x]->find(K + S[x]) != m[x]->end()) ans = min(ans, (*m[x])[K + S[x]] - D[x]);

    for (auto [i, w] : E[x]) {
        if (i != p && i != y) {
            dfs(i, x);

            for (auto [j, d] : *m[i]) {
                ll a = K + 2 * S[x] - j;
                if (m[x]->find(a) != m[x]->end()) ans = min(ans, (*m[x])[a] + d - 2 * D[x]);
            }

            for (auto [j, d] : *m[i]) {
                if (m[x]->find(j) == m[x]->end()) (*m[x])[j] = d;
                else (*m[x])[j] = min((*m[x])[j], d);
            }
        }
    }
}

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]});
    }

    D.assign(n, 0);
    S.assign(n, 0);
    sz.assign(n, 1);
    dfs_sz(0);

    ans = n;
    m.assign(n, {});
    dfs(0);

    return (ans == n ? -1 : ans);
}

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