oj.uz

Submission #1116016

# Submission time Handle Problem Language Result Execution time Memory
1116016 2024-11-21T07:48:06 Z simona1230 Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

long long n,m,k;
long long d[200001];
long long w[200001];
vector<long long> v[200001];

void read()
{
    cin>>n>>m>>k;
    for(long long i=2;i<=n;i++)
    {
        long long p;
        cin>>p;
        v[p].push_back(i);
    }

    for(long long i=1;i<=m;i++)
    {
        long long x;
        cin>>x;
        cin>>d[x]>>w[x];
    }
}

set<long long> s[200001];
map<long long,long long> mp[200001];

void dfs(long long i)
{
    //cout<<i<<endl;
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        dfs(nb);

        for(auto it=s[nb].begin();it!=s[nb].end();it++)
        {
            long long c=*it;
            s[i].insert(c);
            mp[i][c]+=mp[nb][c];
        }
    }

    long long rem=w[i];
    while(rem&&s[i].upper_bound(d[i])!=s[i].end())
    {
        auto it=s[i].upper_bound(d[i]);
        long long in=min(rem,mp[i][*it]);
        mp[i][*it]-=in;
        rem-=in;

        if(mp[i][*it]==0)s[i].erase(*it);
    }
    if(d[i])s[i].insert(d[i]);
    mp[i][d[i]]+=w[i];

    /*cout<<"! "<<i<<endl;
    for(auto it=s[i].begin();it!=s[i].end();it++)
        cout<<*it<<" "<<mp[i][*it]<<endl;*/
}

int main()
{
    read();
    dfs(1);

    long long ans=0;
    for(auto it=s[1].begin();it!=s[1].end();it++)
        ans+=mp[1][*it];
    cout<<ans<<endl;
    return 0;
}

Compilation message

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:34:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 64072 KB Output is correct
2 Execution timed out 2117 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25680 KB Output is correct
2 Correct 8 ms 28064 KB Output is correct
3 Correct 49 ms 47176 KB Output is correct
4 Correct 169 ms 109636 KB Output is correct
5 Execution timed out 2131 ms 1031636 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 42320 KB Output is correct
2 Correct 108 ms 38896 KB Output is correct
3 Correct 114 ms 54856 KB Output is correct
4 Correct 76 ms 37052 KB Output is correct
5 Correct 124 ms 69192 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 5 ms 25168 KB Output is correct
5 Correct 5 ms 25168 KB Output is correct
6 Correct 5 ms 25340 KB Output is correct
7 Correct 4 ms 25168 KB Output is correct
8 Correct 6 ms 25168 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 154 ms 55880 KB Output is correct
11 Correct 141 ms 51528 KB Output is correct
12 Correct 483 ms 207176 KB Output is correct
13 Correct 70 ms 37828 KB Output is correct
14 Correct 563 ms 251732 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27728 KB Output is correct
2 Correct 54 ms 35672 KB Output is correct
3 Correct 60 ms 35444 KB Output is correct
4 Correct 62 ms 35868 KB Output is correct
5 Correct 27 ms 33476 KB Output is correct
6 Correct 1076 ms 491080 KB Output is correct
7 Correct 1102 ms 541064 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 5 ms 25168 KB Output is correct
5 Correct 5 ms 25168 KB Output is correct
6 Correct 5 ms 25340 KB Output is correct
7 Correct 4 ms 25168 KB Output is correct
8 Correct 6 ms 25168 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 5 ms 25680 KB Output is correct
11 Correct 8 ms 28064 KB Output is correct
12 Correct 49 ms 47176 KB Output is correct
13 Correct 169 ms 109636 KB Output is correct
14 Execution timed out 2131 ms 1031636 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25168 KB Output is correct
2 Correct 5 ms 25168 KB Output is correct
3 Correct 5 ms 25168 KB Output is correct
4 Correct 5 ms 25168 KB Output is correct
5 Correct 5 ms 25168 KB Output is correct
6 Correct 5 ms 25340 KB Output is correct
7 Correct 4 ms 25168 KB Output is correct
8 Correct 6 ms 25168 KB Output is correct
9 Correct 6 ms 25168 KB Output is correct
10 Correct 189 ms 64072 KB Output is correct
11 Execution timed out 2117 ms 1048576 KB Time limit exceeded
12 Halted 0 ms 0 KB -