oj.uz

Submission #759364

# Submission time Handle Problem Language Result Execution time Memory
759364 2023-06-16T08:35:48 Z bgnbvnbv Magic Tree (CEOI19_magictree) C++14
13 / 100
 55 ms 25556 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
vector<ll>g[maxN];
map<int,int>mp[maxN];
ll t[maxN],c[maxN];
void dfs(ll u=1)
{
    for(int v:g[u])
    {
        dfs(v);
        if(mp[v].size()>mp[u].size()) mp[u].swap(mp[v]);
        for(auto zz:mp[v]) mp[u][zz.fi]+=zz.se;
        mp[v].clear();
    }
    if(t[u]>0)
    {
        ll tru=c[u];
        while(tru>0)
        {
            auto it=mp[u].lower_bound(t[u]);
            if(it==mp[u].end()) break;
            if(it->se<=tru)
            {
                tru-=it->se;
                mp[u].erase(it);
            }
            else
            {
                it->se-=tru;
                break;
            }
        }
        mp[u][t[u]]+=c[u];
    }
}
ll n,m,k,p[maxN];
void solve()
{
    cin >> n >> m >> k;
    for(int i=2;i<=n;i++) cin >> p[i],g[p[i]].pb(i);
    while(m--)
    {
        ll u;
        cin >> u;
        cin >> t[u] >> c[u];
    }
    ll ans=0;
    dfs();
    for(auto zz:mp[1]) ans+=zz.se;
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 7 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 20988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 20660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 7 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15392 KB Output is correct
2 Correct 29 ms 19168 KB Output is correct
3 Correct 42 ms 19204 KB Output is correct
4 Correct 29 ms 19156 KB Output is correct
5 Correct 15 ms 17824 KB Output is correct
6 Correct 26 ms 21876 KB Output is correct
7 Correct 29 ms 25556 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 7 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Incorrect 7 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -