Submission #964029

#	Time	Username	Problem	Language	Result	Execution time	Memory
964029		MisterReaper	Race (IOI11_race)	C++17	21 / 100	3051 ms	16720 KiB

race

#include <bits/stdc++.h>
#include <race.h>
using i64 = long long;
 
constexpr int maxN = 2E5 + 5;
 
int N, K;
std::vector<std::pair<int, int>> adj[maxN];
std::vector<bool> active;
std::vector<int> sz;
int ans = maxN;

int csizes(int v, int p) {
    sz[v] = 1;
    for(auto [u, w] : adj[v]) {
        if(u == p || !active[u]) {
            continue;
        }
        sz[v] += csizes(u, v);
    }
    return sz[v];
}
int gcent(int v, int p, int S) {
    for(auto [u, w] : adj[v]) {
        if(p == u || !active[u]) {
            continue;
        }
        if(sz[u] * 2 > N) {
            return gcent(u, v, S);
        }
    }
    return v;
}
std::map<int, int> mp;
void paint(int v, int p, int d, int h, bool fill) {
    if(h > K) {
        return;
    }
    if(fill) {
        if(!mp.count(h)) {
            mp[h] = d;
        } else {
            mp[h] = std::min(mp[h], d);
        }
    } else {
        int t = K - h;
        if(mp.count(t)) {
            ans = std::min(ans, d + mp[t]);
        }
    }
    for(auto [u, w] : adj[v]) {
        if(u == p || !active[u]) {
            continue;
        }
        paint(u, v, d + 1, h + w, fill);
    }
}
void decomp(int v) {
    v = gcent(v, v, csizes(v, v));
    active[v] = false;
    mp.clear();
    mp[0] = 0;
    for(auto [u, w] : adj[v]) {
        if(!active[u]) {
            continue;
        }
        paint(u, v, 1, w, 0);
        paint(u, v, 1, w, 1);
    }

    for(auto [u, w] : adj[v]) {
        if(!active[u]) {
            continue;
        }
        decomp(u);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    ::N = N;
    ::K = K;
    active.resize(N, true);
    sz.resize(N);
    for(int i = 0; i < N - 1; i++) {
        // std::cerr << H[i][0] << " " << H[i][1] << " :: " << L[i] << "\n";
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    decomp(0);
 
    if(ans == maxN) {
        ans = -1;
    }
    return ans;
}

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