제출 #1317510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317510		spetr	트리 (IOI24_tree)	C++20	10 / 100	2095 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 =1e17;
    if (abs(l-c) < abs(newc)){
        newc = l-c;
    }
    if (abs(r-c) < abs(newc)){
        newc = r-c;
    }
    if (l <= c && c <= r){
        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: 10 / 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