Submission #834052

#	Time	Username	Problem	Language	Result	Execution time	Memory
834052		NemanjaSo2005	Magic Tree (CEOI19_magictree)	C++17	47 / 100	2080 ms	25048 KiB

magictree

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<int,ll> update[100005];
vector<int> stablo[100005],Brisi;
int N,M,K,rod[100005],vred[100005],kad[100005];
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=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();
//      update[stablo[gde][i]].shrink_to_fit();
   }
   return;
}
int main(){
   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:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    for(int i=1;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:34:11: warning: statement has no effect [-Wunused-value]
   34 |       for(it;it!=update[gde].end();it++){
      |           ^~
magictree.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for(int i=0;i<Brisi.size();i++)
      |                   ~^~~~~~~~~~~~~
magictree.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~

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