oj.uz

Submission #834045

# Submission time Handle Problem Language Result Execution time Memory
834045 2023-08-22T10:21:20 Z NemanjaSo2005 Magic Tree (CEOI19_magictree) C++17
47 / 100
 1414 ms 1048576 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<int,ll> update[1000005];
vector<int> stablo[1000005],Brisi;
int N,M,K,rod[1000005],vred[1000005],kad[1000005];
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();
      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]);
   }
   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

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:33:11: warning: statement has no effect [-Wunused-value]
   33 |       for(it;it!=update[gde].end();it++){
      |           ^~
magictree.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |       for(int i=0;i<Brisi.size();i++)
      |                   ~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70656 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Correct 32 ms 70708 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 33 ms 70740 KB Output is correct
7 Correct 32 ms 70732 KB Output is correct
8 Correct 32 ms 70740 KB Output is correct
9 Correct 33 ms 70732 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 86260 KB Output is correct
2 Runtime error 1390 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70988 KB Output is correct
2 Correct 35 ms 72404 KB Output is correct
3 Correct 53 ms 83284 KB Output is correct
4 Correct 152 ms 121608 KB Output is correct
5 Runtime error 1414 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 79180 KB Output is correct
2 Correct 127 ms 77912 KB Output is correct
3 Correct 132 ms 89604 KB Output is correct
4 Correct 107 ms 77968 KB Output is correct
5 Correct 128 ms 100064 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70656 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Correct 32 ms 70708 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 33 ms 70740 KB Output is correct
7 Correct 32 ms 70732 KB Output is correct
8 Correct 32 ms 70740 KB Output is correct
9 Correct 33 ms 70732 KB Output is correct
10 Correct 138 ms 84176 KB Output is correct
11 Correct 132 ms 82556 KB Output is correct
12 Correct 255 ms 176688 KB Output is correct
13 Correct 92 ms 77892 KB Output is correct
14 Correct 255 ms 205268 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 71628 KB Output is correct
2 Correct 66 ms 73888 KB Output is correct
3 Correct 68 ms 73848 KB Output is correct
4 Correct 69 ms 74060 KB Output is correct
5 Correct 47 ms 72516 KB Output is correct
6 Correct 504 ms 334540 KB Output is correct
7 Correct 492 ms 364620 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70656 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Correct 32 ms 70708 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 33 ms 70740 KB Output is correct
7 Correct 32 ms 70732 KB Output is correct
8 Correct 32 ms 70740 KB Output is correct
9 Correct 33 ms 70732 KB Output is correct
10 Correct 33 ms 70988 KB Output is correct
11 Correct 35 ms 72404 KB Output is correct
12 Correct 53 ms 83284 KB Output is correct
13 Correct 152 ms 121608 KB Output is correct
14 Runtime error 1414 ms 1048576 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70740 KB Output is correct
2 Correct 33 ms 70656 KB Output is correct
3 Correct 33 ms 70740 KB Output is correct
4 Correct 32 ms 70708 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 33 ms 70740 KB Output is correct
7 Correct 32 ms 70732 KB Output is correct
8 Correct 32 ms 70740 KB Output is correct
9 Correct 33 ms 70732 KB Output is correct
10 Correct 115 ms 86260 KB Output is correct
11 Runtime error 1390 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -