Submission #834088

#	Time	Username	Problem	Language	Result	Execution time	Memory
834088		NemanjaSo2005	Magic Tree (CEOI19_magictree)	C++17	100 / 100	110 ms	28904 KiB

magictree

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int max_N=1e5+5;
map<int,ll> update[max_N];
vector<int> stablo[max_N],Brisi;
int N,M,K,rod[max_N],vred[max_N],kad[max_N];
void dfs(int gde){
   if(stablo[gde].size()==0){
      if(kad[gde]==-1)
         return;
      update[gde][kad[gde]]=vred[gde];
      return;
   }
   for(int i=0;i<stablo[gde].size();i++)
      dfs(stablo[gde][i]);
   int najv=stablo[gde][0];
   for(int i=1;i<stablo[gde].size();i++)
      if(update[stablo[gde][i]].size()>update[najv].size())
         najv=stablo[gde][i];
   swap(update[gde],update[najv]);
   for(int i=0;i<stablo[gde].size();i++){
      if(stablo[gde][i]==najv)
         continue;
      int koji=stablo[gde][i];
      for(auto it=update[koji].begin();it!=update[koji].end();it++)
         update[gde][it->first]+=it->second;
   }
   if(kad[gde]!=-1){
      update[gde][kad[gde]]+=vred[gde];
      auto it=update[gde].upper_bound(kad[gde]);
      ll vel=vred[gde];
      Brisi.clear();
      Brisi.shrink_to_fit();
      for(it;it!=update[gde].end();it++){
         if(it->second<=vel){
            vel-=it->second;
            Brisi.push_back(it->first);
         }
         else{
            it->second-=vel;
            break;
         }
      }
      for(int i=0;i<Brisi.size();i++)
         update[gde].erase(Brisi[i]);
   }
   for(int i=0;i<stablo[gde].size();i++){
      update[stablo[gde][i]].clear();
   }
   return;
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M>>K;
   for(int i=2;i<=N;i++){
      cin>>rod[i];
      stablo[rod[i]].push_back(i);
   }
   for(int i=1;i<=N;i++)
      kad[i]=-1;
   int a;
   for(int i=1;i<=M;i++){
      cin>>a;
      cin>>kad[a]>>vred[a];
   }
   dfs(1);
   ll res=0;
   for(auto it=update[1].begin();it!=update[1].end();it++)
      res+=it->second;
   cout<<res<<"\n";
   return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:18:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    for(int i=1;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:35:11: warning: statement has no effect [-Wunused-value]
   35 |       for(it;it!=update[gde].end();it++){
      |           ^~
magictree.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |       for(int i=0;i<Brisi.size();i++)
      |                   ~^~~~~~~~~~~~~
magictree.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17