Submission #753714

#	Time	Username	Problem	Language	Result	Execution time	Memory
753714		nicksms	Race (IOI11_race)	C++17	100 / 100	1928 ms	77880 KiB

race

/**
 *      Author:  Nicholas Winschel
 *      Created: 05.10.2023 22:07:36
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

int best_path(int N, int K, int H[][2], int L[]) {
	V<bool> r(N);
    vi s(N);
    V<V<pi>> a(N);
    if (K==0) return -1;
    for (int i = 0; i < N-1; i++) {
        a[H[i][0]].emplace_back(H[i][1],i);
        a[H[i][1]].emplace_back(H[i][0],i);
    }
    auto dfs = [&](int n, int p, auto &&dfs) -> int {
        s[n]=1;
        for (auto e : a[n]) {
            if (e.f != p && !r[e.f]) s[n] += dfs(e.f,n,dfs);
        }
        return s[n];
    };
    auto gc = [&](int n, int ms, int p, auto &&gc) -> int {
        for (auto e : a[n]) {
            if (e.f != p && !r[e.f]) {
                if (s[e.f] * 2 > ms) return gc(e.f,ms,n,gc);
            }
        }
        return n;
    };
    int best = N+1;
    auto dnq = [&](int n, auto &&dnq) -> void {
        int C = gc(n, dfs(n, -1, dfs), -1, gc);
        // cout << "cent: " << C << endl;

        V<map<ll, int>> cl(sz(a[C]));

        map<ll, pi> bes;

        auto ins= [&](ll d, int dep) {
            // cout << "ins: " << d << " " << dep << endl;
            if (!bes.count(d)) {
                bes[d]={dep,N+1};
                return;
            }
            if (bes[d].f >= dep) {
                bes[d].s=bes[d].f;
                bes[d].f=dep;
                return;
            }
            if (bes[d].s >= dep) {
                bes[d].s=dep;
                return;
            }
        };
        
        auto gn =[&](ll d, int dep) {
            // cout << "gn: " << d << " " << dep << endl;
            if (!bes.count(d)) return N+1;
            // cout << "ret: " << (dep == bes[d].f ? bes[d].s : bes[d].f) << endl;
            return (dep == bes[d].f ? bes[d].s : bes[d].f);
        };

        auto dfs2 =[&](int v, int p, int c, ll d, int dep, auto &&dfs2) -> void {
            if (dep > best || d > K) return;
            if (!cl[c].count(d)) cl[c][d]=dep;
            cl[c][d] = min(cl[c][d], dep);
            for (auto e : a[v]) {
                if (e.f != p && !r[e.f]) {
                    dfs2(e.f, v, c, d+L[e.s], dep+1, dfs2);
                }
            }
        };

        for (int i = 0; i < sz(a[C]); i++) if (!r[a[C][i].f]) {
            // cout << "dir: " << a[C][i].f << endl;
            dfs2(a[C][i].f, C, i, (ll)L[a[C][i].s], 1, dfs2);
            if (cl[i].count(K)) best = min(cl[i][K], best);
            for (auto pr : cl[i]) {
                ins(pr.f, pr.s);
            }
        }
        for (int i = 0; i < sz(a[C]); i++) {
            for (auto pr : cl[i]) {
                best = min(best, pr.s+gn(K-pr.f,cl[i].count(K-pr.f) ? cl[i][K-pr.f] : -1));
            }
        }

        r[C]=1;
        for (auto e : a[C]) {
            if (!r[e.f]) dnq(e.f, dnq);
        }
    };
    dnq(0,dnq);

    return best > N-1 ? -1 : best;
}

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