Submission #1311912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311912		eri16	Tree (IOI24_tree)	C++20	10 / 100	2096 ms	20740 KiB

tree

#include <bits/stdc++.h>
#include "tree.h"
using namespace std;

using ll = long long;

vector <ll> adj[200005];
vector <ll> weight;

ll sm=0;

ll dfs(ll l, ll r, ll node){
    
    ll cursum=0;
    ll amount=0;
    
    for (auto x : adj[node]){
        cursum+=dfs(l,r,x);
    }
    
    if (cursum<l){
        amount=l-cursum;
        sm+=weight[node]*amount;
        return l;
    }
    if (cursum>r){
        amount=cursum-r;
        sm+=weight[node]*amount;
        return r;
    }
    
    return cursum;
}

void init(vector<int> P, vector<int> W){
    
    for (int i=0; i<W.size(); i++){
        weight.push_back(W[i]);
    }
    
    for (int i=1; i<P.size(); i++){
        adj[P[i]].push_back(i);
    }
}

ll query(int L, int R){
    sm=0;
    dfs(L,R,0);
    return sm;
}

• 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