제출 #1241595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241595		alexaaa	트리 (IOI24_tree)	C++20	0 / 100	2117 ms	246080 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(),{});
    set<int> not_found;
    map<int,int>mp;

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

        }
        if(P[i] == -1){
            mp[i] = 1;
            children.push_back({1,i});
        }
        else{
            int rank = mp[P[i]];
            mp[i] = rank + 1;
            children.push_back({mp[i],i});
                
            
        }
        
    }
    
    sort(children.rbegin(),children.rend());
    

   

}
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