Submission #1241653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241653		alexaaa	Tree (IOI24_tree)	C++20	0 / 100	2096 ms	14632 KiB

tree

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>

using namespace std;
vector<int> w;
vector<int> children;
vector<vector<int>> adj_list;
int n;
void init(std::vector<int> P, std::vector<int> W){
    swap(W,w);
    n = P.size();
    adj_list.assign(P.size(),{});
    set<int> not_found;
    stack<int> stack;
    vector<bool> visited(P.size(),false);

    for(int i = 0; i < P.size(); i ++){
        if(P[i] != -1){
            adj_list[P[i]].push_back(i);

        }
        
    }
    stack.push(0);

    while(!stack.empty()){
        int u = stack.top();
        stack.pop();
        if(visited[u]){
            continue;
        }
        visited[u] = true;
        children.push_back(u);
        for(int i = 0; i < adj_list[u].size(); i++){
            int v = adj_list[u][i];
            if (!visited[v]){
                stack.push(v);
            } 

        }


    }
    
    
    

   

}
long long query(int L, int R){
    long long answer = 0;
    vector<int> sum(n);
    for(int i = children.size()-1; i >= 0; i--){
        int u = children[i];
        if(adj_list[u].size() == 0){
            sum[u] = L;
            answer += (L*w[u]);
        }
        else{
            long long total = 0;
            for(auto v : adj_list[u]){
                total+=sum[v];
            }
            if(total < R){
                sum[u] = total;
            }
            else{
                long long dif = R-total;
                answer += (abs(dif)*w[u]);
                sum[u] = total + dif;
            }

        }
        

    }
    return answer;
    
    
    
}

• 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