Submission #942189

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

race

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define ll long long
#define mod 1000000007
#define all(x) x.begin(), x.end()
template <typename T>
using super_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define O_O() ({                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
})
// int dx[]= {-1, 1, 0, 0, -1,-1, 1, 1};
// int dy[]= { 0, 0,-1, 1, -1, 1,-1, 1};

const int N = 2e5 + 9, M = 1e6 + 9;
int n, k, arr[N], ans = mod, siz[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;
}

gp_hash_table < int , int > Sum;

void query(int bap, int dada, int sum, int dep = 1) {
    if(sum > k) return;
    if(Sum.find(k - sum) != Sum.end()) {
        ans = min(ans, dep + Sum[k - sum]);
        // cerr << bap << ' ' << sum << ' ' << dep << ' ' << Sum[k - sum] << endl;
    }
    for(auto[cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        query(cld, bap, sum + val, dep + 1);
    }
}
void update(int bap, int dada, int sum, int dep = 1) {
    if(sum > k) return;
    int mx = Sum[sum];
    if(mx == 0) mx = mod;
    Sum[sum] = min(mod, dep);
    for(auto[cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        update(cld, bap, sum + val, dep + 1);
    }
}

void calculate_ans(int king) {
    Sum.clear();
    Sum[0] = 0;
    for(auto[cld, val] : g[king]) {
        if(virginity[cld]) continue;
        query(cld, cld, val);
        update(cld, cld, val);
    }
}

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);
    }

}

void solve()
{
    solve_sub_prob(1);
}

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);
    }
    n = N; k = K;
    solve();
    if(ans == mod) ans = -1;
    return ans;
}

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