oj.uz

Submission #1116019

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

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

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[100001];
unordered_map<long long,long long> mp[100001];

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 4 ms 12880 KB Output is correct
2 Correct 3 ms 13000 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 54696 KB Output is correct
2 Runtime error 1919 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 4 ms 13260 KB Output is correct
2 Correct 7 ms 15184 KB Output is correct
3 Correct 39 ms 31228 KB Output is correct
4 Correct 147 ms 85324 KB Output is correct
5 Runtime error 1787 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 91 ms 37408 KB Output is correct
2 Correct 90 ms 35036 KB Output is correct
3 Correct 80 ms 46664 KB Output is correct
4 Correct 45 ms 33484 KB Output is correct
5 Correct 83 ms 57160 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12880 KB Output is correct
2 Correct 3 ms 13000 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct
10 Correct 129 ms 47392 KB Output is correct
11 Correct 119 ms 43956 KB Output is correct
12 Correct 418 ms 165192 KB Output is correct
13 Correct 62 ms 34244 KB Output is correct
14 Correct 439 ms 199496 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16976 KB Output is correct
2 Correct 64 ms 31796 KB Output is correct
3 Correct 57 ms 31560 KB Output is correct
4 Correct 72 ms 32012 KB Output is correct
5 Correct 35 ms 29636 KB Output is correct
6 Correct 970 ms 401056 KB Output is correct
7 Correct 1022 ms 438408 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12880 KB Output is correct
2 Correct 3 ms 13000 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct
10 Correct 4 ms 13260 KB Output is correct
11 Correct 7 ms 15184 KB Output is correct
12 Correct 39 ms 31228 KB Output is correct
13 Correct 147 ms 85324 KB Output is correct
14 Runtime error 1787 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 4 ms 12880 KB Output is correct
2 Correct 3 ms 13000 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 12880 KB Output is correct
10 Correct 172 ms 54696 KB Output is correct
11 Runtime error 1919 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -