Submission #834426

#	Time	Username	Problem	Language	Result	Execution time	Memory
834426		HaroldVemeno	Race (IOI11_race)	C++17	100 / 100	664 ms	58368 KiB

race

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

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

struct E {
    int t;
    int w;
};

vector<E> al[200000];
int sts[200000];
bool block[200000];
int n, k;

void calc_sts(int v, int p) {
    if(block[v]) {
        sts[v] = 0;
        return;
    }
    sts[v] = 1;
    for(auto a : al[v]) {
        if(a.t == p) continue;
        calc_sts(a.t, v);
        sts[v] += sts[a.t];
    }
}

int centr_walk(int v) {
    for(auto a : al[v]) {
        if(2*sts[a.t] > sts[v]) {
            sts[v] -= sts[a.t];
            sts[a.t] += sts[v];
            return centr_walk(a.t);
        }
    }
    return v;
}

struct P {
    ll v;
    int l;

    friend bool operator < (const P& a, const P& b) {
        return (a.v < b.v) || (a.v == b.v && a.l < b.l);
    }
};

void paths_dfs(vector<P>& ps, int v, int p, ll d, int l) {
    if(block[v]) return;
    ps.push_back({d, l});
    for(auto a : al[v]) {
        if(a.t == p) continue;
        paths_dfs(ps, a.t, v, d+a.w, l+1);
    }
}

int decomp(int v) {
    if(block[v]) return 2000000;
    calc_sts(v, v);
    v = centr_walk(v);
    set<P> pst;
    pst.insert({0, 0});
    int best = 2000000;
    for(auto a : al[v]) {
        if(block[a.t]) continue;
        vector<P> ps;
        paths_dfs(ps, a.t, v, a.w, 1);
        for(auto p : ps) {
            auto lb = pst.lower_bound({k-p.v, 0});
            if(lb == pst.end()) continue;
            if(lb->v + p.v != k) continue;
            D(lb->v)
            D(lb->l)
            D(p.v)
            D(p.l)
            best = min(best, lb->l+p.l);
        }
        for(auto p : ps) {
            pst.insert(p);
        }
    }
    block[v] = true;
    for(auto a : al[v]) {
        best = min(best, decomp(a.t));
    }
    return best;
}

int best_path(int N, int K, int h[][2], int l[]) {
    n = N; k = K;
    for(int i = 0; i < n-1; ++i) {
        al[h[i][0]].push_back({h[i][1], l[i]});
        al[h[i][1]].push_back({h[i][0], l[i]});
    }
    int r = decomp(0);
    if(r >= 2000000) return -1;
    return r;
}

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