제출 #770089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
770089		vjudge1	경주 (Race) (IOI11_race)	C++17	0 / 100	7 ms	9996 KiB

race

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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;
using ll = long long;
using ld = long double;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 200005, K = 1e6 + 6;

int n, k, id;
vector<pair<int, int>> g[N];
int sz[N], cnt[K], call_id[K];
bool visited[N];

int get_min_cnt(int v) {
    if (v == 0)
        return 0;
    if (v < 0 or k < v or call_id[v] != id)
        return 1e9;
    return cnt[v];
}

void set_min_cnt(int v, int c) {
    cnt[v] = min(get_min_cnt(v), c);
    call_id[v] = id;
}

void compute_size(int u, int p) {
    sz[u] = 1;
    for (auto [v, _] : g[u])
        if (v != p and not visited[v]) {
            compute_size(v, u);
            sz[u] += sz[v];
        }
}
int get_centroid(int u, int p, int n) {
    for (auto [v, _] : g[u])
        if (v != p and not visited[v] and n < 2 * sz[v])
            return get_centroid(v, u, n);
    return u;
}
int get_cnt(int u, int p, bool count_flag, int sum, int depth) {
    int ans = 1e9;
    if (count_flag)
        set_min_cnt(sum, depth);
    else ans = min(ans, get_min_cnt(k - sum) + depth);
    for (auto [v, l] : g[u])
        if (v != p and not visited[v])
            ans = min(ans, get_cnt(v, u, count_flag, sum + l, depth + 1));
    return ans;
}
int build(int u) {
    compute_size(u, -1);
    int centroid = get_centroid(u, -1, sz[u]);
    visited[centroid] = true;
    int ans = 1e9;
    ++id;
    for (auto [v, l] : g[centroid])
        if (not visited[v]) {
            ans = min(ans, get_cnt(v, centroid, false, l, 1));
            get_cnt(v, centroid, true, l, 1);
        }
    for (auto [v, _] : g[centroid])
        if (not visited[v])
            ans = min(ans, build(v));
    return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    for (int i = 0; i + 1 < n; ++i) {
        g[H[i][0]].emplace_back(H[i][1], L[i]);
        g[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    int ans = build(0);
    if (ans >= n)
        ans = -1;
    return ans;
}

// int main() {
//     ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
//     int h[][2]{
//         {0, 1},
//         {0, 2},
//         {2, 3},
//         {3, 4},
//         {4, 5},
//         {0, 6},
//         {6, 7},
//         {6, 8},
//         {8, 9},
//         {8, 10}
//     };
//     int l[]{
//         3, 4, 5, 4, 6, 3, 2, 5, 6, 7
//     };
//     cout << best_path(11, 12, h, l) << '\n';
//     return 0;
// }

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