Submission #1317538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317538		spetr	트리 (IOI24_tree)	C++20	13 / 100	2096 ms	30720 KiB

tree

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>


vll tree;
vl weights;
vl c;
vl parents;
vl w;
vl subs;

pl dfs(ll v, ll p, ll l){
    ll minimum = w[v];
    ll idx = v;
    for (auto x : tree[v]){
        if (subs[x] > l && x != p){
            auto sub = dfs(x, v, l);
            if (sub.second < minimum){
                minimum = sub.second;
                idx = sub.first;
            }
        }
    }

    return {idx, minimum};
}


long long query(int L, int R){
    ll n = tree.size();
    c.clear(); c.resize(n,0);
    subs.clear(); subs.resize(n,0);
    for (ll i = 1; i < n; i++){
        if (tree[i].size() == 1){
            c[i] = L;
            subs[i] = L;
        }
    }

    for (ll i = n-1; i >= 0; i--){
        ll suma = subs[i];
        for (ll j = 0; j < tree[i].size(); j++){
            if (tree[i][j] != parents[i]){
                suma += subs[tree[i][j]];
            }
        }
        subs[i] = suma;
        while (subs[i] > R){
            auto x = dfs(i, parents[i], L);
            ll pos = x.first;
            
            ll k = subs[i]-R;
            while (pos != i){
                k = min(k, subs[pos]-L);
                pos = parents[pos];
            }
            pos = x.first;
            c[pos]-=k;
            subs[i]-=k;
            while (pos != i){
                subs[pos]-=k;
                pos = parents[pos];
            }

        }


    }
    ll price = 0;
    for (ll i = 0; i < n; i++){
        price += w[i]*abs(c[i]);
    }
    return price;
}


void init(std::vector<int> P, std::vector<int> W){
    for (ll i = 0; i < W.size(); i++){weights.push_back(W[i]);}

    tree.resize(P.size());
    for (ll i = 1; i < P.size(); i++){
        tree[i].push_back(P[i]);
        tree[P[i]].push_back(i);
    }
    for (ll i = 0; i <P.size(); i++){
        parents.push_back(P[i]);
        w.push_back(W[i]);
    }
}



/*/int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);




    return 0;
}/*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19