제출 #942148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942148		R_i_n_Nabil	경주 (Race) (IOI11_race)	C++17	0 / 100	2 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], 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;
    euler[timer] = curr_val;
    depth[timer] = dep;
    for(auto[cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        euler_tour(cld, bap, (ll)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;
            ll need = k - euler[i];
            auto it = gp.find(need);
            if(it != gp.end()) {
                ans = min(ans, depth[i] + gp[need]);
            }
        }
        // Update
        for(int i = in[cld]; i <= out[cld]; i++) {
            if(euler[i] > k) continue; 
            auto it = gp.find(euler[i]);
            if(it == gp.end()) {
                gp[euler[i]] = depth[i];
            }
            else {
                gp[euler[i]] = min(depth[i], gp[euler[i]]);
            }
        }
    }
}

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

    calculate_ans(king);

    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] + 1, v = H[i][1] + 1, w = L[i];
        g[u].emplace_back(v, w), g[v].emplace_back(u, w);
    }
    n = N; k = K;
    solve_sub_prob(1);
    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;
//         pr[i].first++;
//         pr[i].second++;
//     }
//     for (int i = 1; i < n; i++)
//     {
//         cin >> arr[i];
//         g[pr[i].first].push_back({pr[i].second, arr[i]});
//         g[pr[i].second].push_back({pr[i].first, arr[i]});
//     }
//     solve_sub_prob(1);
//     if (ans < mod)
//         cout << ans << endl;
//     else
//         cout << -1 << endl;
// }

// int main()
// {
//     // freopen("input.txt","r",stdin);
//     O_O();
//     int test = 1;
//     for (int tc = 1; tc <= test; tc++)
//     {
//         solve();
//     }

//     return 0;
// }

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