Submission #1222054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222054		elaksher	Race (IOI11_race)	C++20	100 / 100	660 ms	43300 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long, null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update>;

const int N = 2e5 + 5;
vector<pair<int, long long>> g[N];
int sz[N], is_removed[N];
int k, ans = 1e9, n;
map<long long, int> cnt;
int get_sz(int u, int p)
{
    sz[u] = 1;
    for (auto [v, _] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        sz[u] += get_sz(v, u);
    }
    return sz[u];
}
 
int get_cent(int u, int p, int cur_sz)
{
    for (auto [v, _] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        if (sz[v] * 2 > cur_sz)
            return get_cent(v, u, cur_sz);
    }
    return u;
}
void dfs(int v, int p, int depth, int delta, long long w)
{
    if(cnt.count(w))    
        cnt[w] = min(cnt[w], depth);
    else cnt[w] = depth;
    for (auto [u, W] : g[v])
    {
        if (u == p || is_removed[u])
            continue;
        dfs(u, v, depth + 1, delta, w + W);
    }
}
void get_ans(int u, int p, int depth, long long w)
{
    if (k - w >= 0 && cnt.count(k - w))
        ans = min(ans, cnt[k - w] + depth);
    for (auto [v, W] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        get_ans(v, u, depth + 1, W + w);
    }
}
 
void comp(int v)
{
    int size = get_sz(v, -1), cent = get_cent(v, -1, size);
    cnt[0] = 0;
    for (auto [u, w] : g[cent])
    {
        if (is_removed[u])
            continue;
        get_ans(u, cent, 1, w);
        dfs(u, cent, 1, 1, w);
    }
    cnt.clear();
    is_removed[cent] = 1;
    for (auto [u, _] : g[cent])
    {
        if (is_removed[u])
            continue;
        comp(u);
    }
}
 
// int32_t main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
//     cin >> n >> k;
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         g[u].push_back({v, w});
//         g[v].push_back({u, w});
//     }
//     comp(0);
//     cout << ans;
//     return 0;
// }

int best_path(int _n, int _k, int h[][2], int l[]) {
    n = _n;
    k = _k;
    for (int i = 0; i < n-1; i++) {
        g[h[i][0]].emplace_back(h[i][1], l[i]);
        g[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    comp(0);
    return ans == 1e9 ? -1 : ans;
}

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