Submission #1241594

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

tree

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#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++){
        
      long long total = 0;
      int u = children[i].second;
      if(adj_list[u].size() == 0){
        answer += (L * w[children[i].second]);
        sum[children[i].second] = L;

      }
      else{
          for(int j = 0; j < adj_list[u].size(); 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;
            cout << diff << '\n';
            answer += (abs(diff)*w[children[i].second]);
            sum[children[i].second] = total + diff;
            cout << children[i].second <<" " <<total + diff << '\n';
          }

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