oj.uz

Submission #1116021

# Submission time Handle Problem Language Result Execution time Memory
1116021 2024-11-21T07:52:56 Z simona1230 Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 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];
    auto it=s[i].upper_bound(d[i]);
    while(rem&&it!=s[i].end())
    {
        long long in=min(rem,mp[i][*it]);
        mp[i][*it]-=in;
        rem-=in;
        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 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 4 ms 13048 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 4 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 13004 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 54612 KB Output is correct
2 Execution timed out 2076 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 44 ms 30288 KB Output is correct
2 Correct 45 ms 32248 KB Output is correct
3 Correct 44 ms 31048 KB Output is correct
4 Runtime error 1821 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 37704 KB Output is correct
2 Correct 89 ms 34888 KB Output is correct
3 Correct 79 ms 46676 KB Output is correct
4 Correct 43 ms 33480 KB Output is correct
5 Correct 70 ms 55368 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 4 ms 13048 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 4 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 13004 KB Output is correct
10 Correct 146 ms 51028 KB Output is correct
11 Correct 133 ms 46364 KB Output is correct
12 Correct 354 ms 169288 KB Output is correct
13 Correct 62 ms 33476 KB Output is correct
14 Correct 446 ms 208812 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16976 KB Output is correct
2 Correct 49 ms 31052 KB Output is correct
3 Correct 43 ms 31056 KB Output is correct
4 Correct 64 ms 31268 KB Output is correct
5 Correct 41 ms 29648 KB Output is correct
6 Correct 1553 ms 665928 KB Output is correct
7 Runtime error 1640 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 4 ms 13048 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 4 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 13004 KB Output is correct
10 Correct 44 ms 30288 KB Output is correct
11 Correct 45 ms 32248 KB Output is correct
12 Correct 44 ms 31048 KB Output is correct
13 Runtime error 1821 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 4 ms 12880 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 4 ms 13048 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 4 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 3 ms 13004 KB Output is correct
10 Correct 161 ms 54612 KB Output is correct
11 Execution timed out 2076 ms 1048576 KB Time limit exceeded
12 Halted 0 ms 0 KB -