Submission #884182

#	Time	Username	Problem	Language	Result	Execution time	Memory
884182		kh0i	Race (IOI11_race)	C++17	0 / 100	4 ms	15196 KiB

race

#include "bits/stdc++.h"
#include <race.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 2e5 + 3;
const int K = 1e6 + 3;

int n, k;
vector<pii> g[N];
int sz[N], dep[N], h[N];
int mn[K];
int res = 0x3f3f3f3f;
bool del[N];

int dfs_sz(int u, int pre){
    sz[u] = 1;
    for(auto [v, w] : g[u])
        if(v != pre and !del[v])
            sz[u] += dfs_sz(v, u);
    return sz[u];
}

int find_centroid(int u, int pre, int n){
    for(auto [v, w] : g[u])
        if(v != pre and !del[v])
            if(2 * sz[v] > n)
                return find_centroid(v, u, n);
    return u;
}

void dfs(int u, int pre, bool upd){
    if(dep[u] > k)
        return;
    if(upd)
        mn[dep[u]] = min(mn[dep[u]], h[u]);
    else
        res = min(res, h[u] + mn[k - dep[u]]);
    for(auto [v, w] : g[u]){
        if(v == pre or del[v])
            continue;
        dep[v] = dep[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u, upd);
    }
}

void clean(int u, int pre){
    if(dep[u] > k)
        return;
    mn[u] = 0x3f3f3f3f;
    for(auto [v, w] : g[u])
        if(v != pre and !del[v])
            clean(v, u);
}

void calc(int u, int pre){
    int c = find_centroid(u, pre, dfs_sz(u, pre));
    debug(u, c);
    del[c] = 1;

    dep[c] = h[c] = 0;
    for(auto [v, w] : g[c]){
        if(v != pre and !del[v]){
            dep[v] = dep[c] + w;
            h[v] = h[c] + 1;
            dfs(v, c, 0);
            dfs(v, c, 1);
        }
    }

    for(auto [v, w] : g[c])
        if(v != pre and !del[v])
            clean(v, c);

    for(auto [v, w] : g[c])
        if(v != pre and !del[v])
            calc(v, c);
}

void solve(){
    cin >> n >> k;
    for(int i = 1; i < n; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    memset(mn, 0x3f3f3f3f, sizeof(mn));
    mn[0] = 0;
    calc(0, -1);
    debug(res);
    cout << (res > n ? -1 : res);
}

int best_path(int _n, int _k, int H[][2], int L[]){
    n = _n, k = _k;
    memset(mn, 0x3f3f3f3f, sizeof(mn));
    for(int i = 0; i < n - 1; ++i){
        int u = H[i][0], v = H[i][1], w = L[i];
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    mn[0] = 0;
    calc(0, -1);
    return (res > n ? -1 : res);
}

// int32_t main() {
//     cin.tie(nullptr)->sync_with_stdio(0);
//     #define task "troll"
//     if(fopen(task".inp", "r")){
//         freopen(task".inp", "r", stdin);
//         freopen(task".out", "w", stdout);
//     }
//     int test = 1;
// //    cin >> test;
//     for(int i = 1; i <= test; ++i){
// //        cout << "Case #" << i << ": ";
//         solve();
//     }
//     #ifdef LOCAL
//         cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
//     #endif
//     return 0;
// }

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