Submission #942173

#	Time	Username	Problem	Language	Result	Execution time	Memory
942173		R_i_n_Nabil	Race (IOI11_race)	C++17	0 / 100	3 ms	12636 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define ll long long
#define mod 1000000007

const int N = 2e5 + 40, M = 1e6 + 9;
int n, k, ans = mod, siz[N], in[N], out[N], depth[N], flat[N], timer = 0;
ll euler[N];

vector < pair < int , int > > g[N];
bitset < N > virginity;

void dfs(int bap, int dada) {
    siz[bap] = 1;
    for(auto [cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        dfs(cld, bap);
        siz[bap] += siz[cld];
    }
}

int find(int bap, int dada, int sz) {
    for(auto [cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        if(siz[cld] > sz) return find(cld, bap, sz);
    }
    return bap;
}

void euler_tour(int bap, int dada, ll curr_val = 0, int dep = 0) {
    in[bap] = ++timer;
    flat[timer] = bap;
    euler[bap] = curr_val;
    depth[bap] = dep;
    for(auto[cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        euler_tour(cld, bap, val + curr_val, dep + 1);
    }
    out[bap] = timer;
}

void calculate_ans(int king) {
    timer = 0;
    euler_tour(king, king);

    gp_hash_table < ll , int > gp;
    gp[0] = 0;

    for(auto[cld, val] : g[king]) {
        // Query
        for (int i = in[cld]; i <= out[cld]; i++)
        {
           // if(euler[i] > k) continue;
            int v = flat[i];
            ll need = k - euler[v];
            auto it = gp.find(need);
            if(it != gp.end()) {
                ans = min(ans, depth[v] + gp[need]);
            }
        }
        // Update
        for(int i = in[cld]; i <= out[cld]; i++) {
            //if(euler[i] > k) continue; 
            int v = flat[i];
            auto it = gp.find(euler[v]);
            if(it == gp.end()) {
                gp[euler[v]] = depth[v];
            }
            else {
                gp[euler[v]] = min(depth[v], gp[euler[v]]);
            }
        }
    }
}

void solve_sub_prob(int curr) {
    dfs(curr, curr);
    int king = find(curr, curr, siz[curr] / 2);

    calculate_ans(king);
    virginity[king] = 1;

    for(auto [cld, val] : g[king]) {
        if(virginity[cld]) continue;
        solve_sub_prob(cld);
    }

}

int best_path(int N, int K, int H[][2], int L[])
{
    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);
    }
    k = K;
    solve_sub_prob(0);

    if(ans == mod) ans = -1;
    return ans;
}

// void solve()
// {
//     cin >> n >> k;
//     pair<int, int> pr[n + 9];
//     for (int i = 1; i < n; i++)
//     {
//         cin >> pr[i].first >> pr[i].second;
//     }
//     for (int i = 1; i < n; i++)
//     {
//         int x; cin >> x;
//         g[pr[i].first].push_back({pr[i].second,x});
//         g[pr[i].second].push_back({pr[i].first, x});
//     }
//     solve_sub_prob(0);
//     if (ans < mod)
//         cout << ans << endl;
//     else
//         cout << -1 << endl;
// }

// int main()
// {
//    solve();

//     return 0;
// }

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