oj.uz

Submission #834058

# Submission time Handle Problem Language Result Execution time Memory
834058 2023-08-22T10:26:14 Z NemanjaSo2005 Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 25000 KB 
#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(){
   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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7360 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12128 KB Output is correct
2 Execution timed out 2069 ms 16228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 6 ms 7552 KB Output is correct
3 Correct 13 ms 7508 KB Output is correct
4 Correct 65 ms 24168 KB Output is correct
5 Execution timed out 2054 ms 25000 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10068 KB Output is correct
2 Correct 44 ms 10160 KB Output is correct
3 Correct 55 ms 16020 KB Output is correct
4 Correct 31 ms 14536 KB Output is correct
5 Correct 43 ms 24148 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7360 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 48 ms 10160 KB Output is correct
11 Correct 47 ms 10156 KB Output is correct
12 Correct 96 ms 16032 KB Output is correct
13 Correct 29 ms 14548 KB Output is correct
14 Correct 115 ms 24176 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8004 KB Output is correct
2 Correct 20 ms 10204 KB Output is correct
3 Correct 25 ms 10196 KB Output is correct
4 Correct 22 ms 10196 KB Output is correct
5 Correct 9 ms 9044 KB Output is correct
6 Correct 203 ms 12420 KB Output is correct
7 Correct 216 ms 15956 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7360 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 4 ms 7508 KB Output is correct
11 Correct 6 ms 7552 KB Output is correct
12 Correct 13 ms 7508 KB Output is correct
13 Correct 65 ms 24168 KB Output is correct
14 Execution timed out 2054 ms 25000 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7360 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7252 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 66 ms 12128 KB Output is correct
11 Execution timed out 2069 ms 16228 KB Time limit exceeded
12 Halted 0 ms 0 KB -