oj.uz

Submission #1116017

# Submission time Handle Problem Language Result Execution time Memory
1116017 2024-11-21T07:49:07 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    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 6 ms 25168 KB Output is correct
5 Correct 4 ms 25184 KB Output is correct
6 Correct 5 ms 25336 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 64332 KB Output is correct
2 Execution timed out 2058 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 6 ms 25680 KB Output is correct
2 Correct 10 ms 28032 KB Output is correct
3 Correct 47 ms 47184 KB Output is correct
4 Correct 141 ms 108360 KB Output is correct
5 Execution timed out 2139 ms 1048576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 42312 KB Output is correct
2 Correct 125 ms 38852 KB Output is correct
3 Correct 89 ms 54276 KB Output is correct
4 Correct 56 ms 36548 KB Output is correct
5 Correct 88 ms 66680 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 6 ms 25168 KB Output is correct
5 Correct 4 ms 25184 KB Output is correct
6 Correct 5 ms 25336 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 141 ms 56052 KB Output is correct
11 Correct 146 ms 51712 KB Output is correct
12 Correct 498 ms 207280 KB Output is correct
13 Correct 39 ms 37184 KB Output is correct
14 Correct 554 ms 251676 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 27772 KB Output is correct
2 Correct 51 ms 35144 KB Output is correct
3 Correct 57 ms 35144 KB Output is correct
4 Correct 43 ms 35400 KB Output is correct
5 Correct 22 ms 33228 KB Output is correct
6 Correct 1041 ms 490700 KB Output is correct
7 Correct 1109 ms 540404 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 6 ms 25168 KB Output is correct
5 Correct 4 ms 25184 KB Output is correct
6 Correct 5 ms 25336 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 6 ms 25680 KB Output is correct
11 Correct 10 ms 28032 KB Output is correct
12 Correct 47 ms 47184 KB Output is correct
13 Correct 141 ms 108360 KB Output is correct
14 Execution timed out 2139 ms 1048576 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 6 ms 25168 KB Output is correct
5 Correct 4 ms 25184 KB Output is correct
6 Correct 5 ms 25336 KB Output is correct
7 Correct 5 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 5 ms 25168 KB Output is correct
10 Correct 147 ms 64332 KB Output is correct
11 Execution timed out 2058 ms 1048576 KB Time limit exceeded
12 Halted 0 ms 0 KB -