Submission #1241491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241491		alexaaa	Tree (IOI24_tree)	C++20	0 / 100	2092 ms	15916 KiB

tree

#include<iostream>
#include<vector>
#include<algorithm>
#include "tree.h"



using namespace std;
vector<int> w;
vector<pair<int,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(),{});
    for(int i = 0; i < P.size(); i ++){
        if(P[i] != -1){
            adj_list[P[i]].push_back(i);

        }
    }
    for(int i = 0; i < P.size(); i++){
        children.push_back({adj_list[i].size(),i});
    }
    sort(children.begin(),children.end());

   

}
long long query(int L, int R){
    long long answer = 0;
    vector<long long> sum(n);
    for(int i = 0; i < n; i++){
        if(children[i].first == 0){
            answer += (L * w[children[i].second]);
            sum[children[i].second] = L;
        }
        else{
            long long total = 0;
            int u = children[i].second;
            for(int j = 0; j < children[i].first; j++){
                total += sum[adj_list[u][j]];
            }
            if(total < R){
                answer += (0*w[children[i].second]);
                sum[children[i].second] = total;
            }
            else{
                int diff = R - total;
                answer += (abs(diff)*w[children[i].second]);
                sum[children[i].second] = total + diff;
            }
        }
    }
    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