Submission #1317504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317504		spetr	Tree (IOI24_tree)	C++20	0 / 100	2094 ms	26348 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;

pl dfs(ll v, ll p, ll l, ll r){
    ll c = 0;
    ll total = 0;
    for (auto x : tree[v]){
        if (x != p){
            auto sub = dfs(x, v, l, r);
            c += sub.first;
            total += sub.second;
        }
    }
    ll newc;
    if (c < l){
        newc = l-c;
    }
    else if (c > r){
        newc = c-r;
    }
    else{
        newc = 0;
    }

    c += newc;
    total += abs(newc)*weights[v];
    return {c, total};
}


long long query(int L, int R){
    auto x = dfs(0,-1,L,R);
    return x.second;
}


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



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




    return 0;
}/*/

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