Submission #99478

#	Time	Username	Problem	Language	Result	Execution time	Memory
99478		naoai	Race (IOI11_race)	C++14	100 / 100	652 ms	69884 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

typedef long long i64;
const int nmax = 2e5;

static i64 K;
static int ans;
static int lant[nmax + 1], sz[nmax + 1];
static i64 ct[nmax + 1];

static vector<pair<int, int>> g[nmax + 1];
static set<pair<i64, int>> s[nmax + 1];

void dfs (int nod, int h, int dad = -1) {
    sz[nod] = 1;

    int mxf = -1, mxg = -1, valm = 0;

    for (auto i : g[nod]) {
        if (i.first != dad) {
            dfs(i.first, h + 1, nod);

            sz[nod] += sz[i.first];
            if (sz[i.first] > mxg) {
                mxg = sz[i.first];
                mxf = i.first;
                valm = i.second;
            }
        }
    }

    if (mxf == -1) {
        lant[nod] = nod;
    } else {
        lant[nod] = lant[mxf];
    }

    ct[lant[nod]] += valm;

    set<pair<i64, int>>::iterator it = s[lant[nod]].lower_bound({K - ct[lant[nod]], 0});
    if (it != s[lant[nod]].end())
        if ((it -> first) == K - ct[lant[nod]]) {
            ans = min(ans, (it -> second) - h);
        }
    s[lant[nod]].insert({-ct[lant[nod]], h});

    for (auto i : g[nod]) {
        if (i.first == mxf || i.first == dad)
            continue;

        int l = lant[i.first];
        ct[l] += i.second;

        for (auto x : s[l]) {
            it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - x.first - ct[l], 0});
            if (it != s[lant[nod]].end())
                if ((it -> first) == K - ct[lant[nod]] - x.first - ct[l]) {
                    ans = min(ans, x.second + (it -> second) - 2 * h);
                }
        }

        while (!s[l].empty()) {
            pair<i64, int> x = *s[l].begin();
            x.first += ct[l];
            s[l].erase(s[l].begin());
            s[lant[nod]].insert({x.first - ct[lant[nod]], x.second});
        }
    }
}

int best_path (int n, int k, int h[][2], int l[]) {
    K = k;
    for (int i = 0; i < n - 1; ++ i) {
        g[h[i][0]].push_back({h[i][1], l[i]});
        g[h[i][1]].push_back({h[i][0], l[i]});
    }

    ans = n + 1;
    dfs(0, 0);

    if (ans == n + 1)
        ans = -1;
    return ans;
}

/*int main() {
    int a[11][2]= {0, 1,
0, 2,
2, 3,
3, 4,
4, 5,
0, 6,
6, 7,
6, 8,
8, 9,
8, 10};
    int b[11] = {3,4,5,4,6,3,2,5,6,7};

    //int a[3][2]= {0, 1, 1, 2, 1, 3 };
    //int b[3] = {1, 2, 4};
    cout << best_path (11, 12, a, b) << "\n";
    return 0;
}*/

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