Submission #1013681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013681		0x34c	Race (IOI11_race)	C++17	100 / 100	383 ms	55596 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pii pair<ll, ll>
#define endl '\n'

using namespace std;
using namespace __gnu_pbds;


ll N, K;
vector<vector<pii>> graph;
vector<ll> sz;
vector<bool> vis;
gp_hash_table<ll, ll> short_pth;
const ll INF = 1e14;


ll find_size(ll v, ll p = -1) {
    sz[v] = 1;
    for(pii e : graph[v]) {
        ll u = e.first;
        if(vis[u] || u == p) continue;
        sz[v] += find_size(u, v);
    }

    return sz[v];
}

ll find_centroid(ll v, ll p, ll n) {
    for(pii e : graph[v]) {
        ll u = e.first;
        if(u == p || vis[u]) continue;
        if(sz[u] > n / 2) return find_centroid(u, v, n);
    }

    return v;
}

void find_bst_path(ll v, ll p, ll w, ll d, ll &bst_path, bool upd) {
    if(w > K) return;
    if(upd)
        short_pth[w] = min(short_pth.find(w) != short_pth.end() ? short_pth[w] : INF, d);
    else if(short_pth.find(K - w) != short_pth.end())
        bst_path = min(bst_path, d + short_pth[K - w]);

    for(pii u : graph[v]) {
        if(vis[u.first] || u.first == p) continue;
        find_bst_path(u.first, v, w + u.second, d + 1, bst_path, upd);
    }
}

void centroid(ll v, ll &bst_path) {
    find_size(v);
    
    ll c = find_centroid(v, -1, sz[v]);

    vis[c] = true;
    short_pth[0] = 0;

    for(pii e : graph[c]) {
        ll u = e.first;
        if(vis[u]) continue;
        find_bst_path(u, c, e.second, 1, bst_path, false);
        find_bst_path(u, c, e.second, 1, bst_path, true);
    }
    
    short_pth.clear();

    for(pii e : graph[c]) {
        ll u = e.first;
        if(!vis[u]) centroid(u, bst_path);
    }
}


int best_path(int n, int k, int H[][2], int L[])
{
    N = n; K = k;
    graph.resize(N);
    sz.resize(N);
    vis.resize(N, false);

    for(ll i = 0; i < N - 1; i++) {
        graph[H[i][0]].push_back({H[i][1], L[i]});
        graph[H[i][1]].push_back({H[i][0], L[i]});
    }

    ll bst_path = INF;
    centroid(0, bst_path);

    return bst_path == INF ? -1 : bst_path;
}

// signed main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);

//     ll n, k;
//     cin >> n >> k;

//     ll H[n - 1][2], L[n - 1];
//     for(ll i = 0; i < n - 1; i++) {
//         cin >> H[i][0] >> H[i][1] >> L[i];
//     }

//     ll sol; cin >> sol;

//     ll bst = best_path(n, k, H, L);
//     cout << "AC Solution : " << sol << endl;
//     cout << "User Solution : " << bst << endl;
// }

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