Submission #99409

#	Time	Username	Problem	Language	Result	Execution time	Memory
99409		naoai	Race (IOI11_race)	C++14	0 / 100	14 ms	14464 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;
bool viz[nmax + 1];
int lant[nmax + 1], sz[nmax + 1];
i64 ct[nmax + 1];

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

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

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

    for (auto i : g[nod]) {
        if (viz[i.first] == 0) {
            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, 0});
    if (it != s[lant[nod]].end() && (it -> first) == K - ct[lant[nod]]) {
        ans = min(ans, (it -> second) - h);
    }
    s[lant[nod]].insert({0, h});

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

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

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

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

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


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

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