제출 #1274201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274201		get_ducked	경주 (Race) (IOI11_race)	C++20	0 / 100	1 ms	568 KiB

race

//بسم الله الرحمان الرحيم
//we are the winners
//we are the champions

#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;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb emplace_back
#define lv (v<<1)
#define rv ((v<<1)|1)
#define endl '\n'

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<int M>
struct Cyclic {
    int val = 0;
    Cyclic() = default;
    Cyclic(int _val) : val(_val) {}
    Cyclic(ll _val) : val((int)_val) {}
    Cyclic(const Cyclic& other) : val(other.val) {}

    Cyclic operator+(const Cyclic& other) const {
        return Cyclic((val + other.val) % M);
    }
    Cyclic operator-(const Cyclic& other) const {
        return Cyclic((val - other.val + M) % M);
    }
    Cyclic operator*(const Cyclic& other) const {
        return Cyclic(1LL * val * other.val % M);
    }
    Cyclic operator/(const Cyclic& other) const {
        return (*this) * other.inv();
    }
    Cyclic& operator+=(const Cyclic& other) {
        val = (val + other.val) % M;
        return (*this);
    }
    Cyclic& operator-=(const Cyclic& other) {
        val = (val - other.val + M) % M;
        return (*this);
    }
    Cyclic& operator*=(const Cyclic& other) {
        val = 1LL * val * other.val % M;
        return (*this);
    }
    Cyclic& operator/=(const Cyclic& other) {
        (*this) = (*this) / other;
        return (*this);
    }

    Cyclic pow(ll p) const {
        Cyclic res(1), base(val);
        while (p > 0) {
            if (p & 1) res *= base;
            base *= base;
            p >>= 1;
        }
        return res;
    }
    Cyclic inv() const {
        assert(val != 0);
        return pow(M-2);
    }

    static Cyclic pow(ll a, ll p) {
        return Cyclic(a).pow(p);
    }

    friend istream& operator>>(istream& is, Cyclic& c) {
        is >> c.val;
        return is;
    }
    friend ostream& operator<<(ostream& os, const Cyclic& c) { return os << c.val; }
};

constexpr int MOD = 998244353;
typedef Cyclic<MOD> cint;

int ans, k;
struct Centroid_Decomposition {
    /* Internals */
    const int root = 0;
    const vector<vector<pii>>& adj;
    vi sub_sz, is_centroid;

    /* Problem Specific */
    // ...

    /* Initialize the Centroid Decomposition */
    Centroid_Decomposition(int n, const vector<vector<pii>> &g)
        : adj(g), sub_sz(n+1, 0), is_centroid(n+1, 0) {}

    /* Update subtree size of each node */
    int updateSize(int u, int p = -1){
        sub_sz[u] = 1;
        for (auto [v, w] : adj[u])
            if (v != p && !is_centroid[v])
                sub_sz[u] += updateSize(v, u);
        return sub_sz[u];
    }

    /* Get centroid of subtree rooted at u */
    int getCentroid(int u, int target, int p = -1){
        for(auto [v, w] : adj[u]){
            if(v == p || is_centroid[v]) continue;
            if((sub_sz[v]>>1) > target)
                return getCentroid(v, target, u);
        }
        return u;
    }

    void update_ans(int u, int p, int dep_cent, int dist_cent, const unordered_map<int, int>& other) {
        if (dist_cent > k) return;
        auto cand = other.find(k-dist_cent);
        if (cand != other.end()) {
            ans = min(ans, cand->second+dep_cent);
        }
        for (auto& [nxt, w] : adj[u]) {
            if(nxt == p || is_centroid[nxt]) continue;
            update_ans(nxt, u, dep_cent+1, dist_cent+w, other);
        }
    }

    void update_lens(int u, int p, int dep_cent, int dist_cent, unordered_map<int, int>& other) {
        if (dist_cent > k) return;
        auto cand = other.find(dist_cent);
        if (cand != other.end()) {
            cand->second = min(cand->second, dep_cent);
        } else {
            other[dist_cent] = dep_cent;
        }
        for (auto& [nxt, w] : adj[u]) {
            if(nxt == p || is_centroid[nxt]) continue;
            update_lens(nxt, u, dep_cent+1, dist_cent+w, other);
        }
    }

    /* Decompose tree into centroid tree */
    void Centroid(int u, int p){
        int centroidPoint = getCentroid(u, updateSize(u));
        is_centroid[centroidPoint] = true;

        // do something with centroid
        unordered_map<int, int> lens;
        lens[0] = 0;
        for(auto [v, w] : adj[centroidPoint]){
            if(is_centroid[v]) continue;
            update_ans(v, centroidPoint, 1, w, lens);
            update_lens(v, centroidPoint, 1, w, lens);
        }

        for(auto [v, w] : adj[centroidPoint]){
            if(is_centroid[v]) continue;
            // prepare for a dive
            Centroid(v, centroidPoint);
            // recover
        }

        // do something with centroid
    }

    // Call this function to decompose the tree
    void Decompose(){ Centroid(root, root-1); }
};

int best_path(int n, int _k, int e[][2], int w[]) {
    k = _k;
    ans = n;
    vector<vector<pii>> adj(n);
    rep(i, 0, n-1) {
        adj[e[i][0]].pb(e[i][1], w[i]);
        adj[e[i][1]].pb(e[i][0], w[i]);
    }
    Centroid_Decomposition cent(n, adj);
    cent.Decompose();
    if (ans == n) return -1;
    return 1;
}

// int main() {
// #ifdef LOCAL
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
//     IOS
//
//     int n;
//     cin >> n >> k;
//
//
//     return 0;
// }

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