oj.uz

Submission #759367

# Submission time Handle Problem Language Result Execution time Memory
759367 2023-06-16T08:36:41 Z bgnbvnbv Magic Tree (CEOI19_magictree) C++14
16 / 100
 104 ms 27680 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;
#define int ll
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;
}
 main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

magictree.cpp:63:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 |  main()
      |  ^~~~

Subtask #1
0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20352 KB Output is correct
2 Correct 38 ms 27680 KB Output is correct
3 Correct 104 ms 25164 KB Output is correct
4 Correct 54 ms 23312 KB Output is correct
5 Correct 74 ms 25744 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 10 ms 15252 KB Output is correct
2 Correct 31 ms 18752 KB Output is correct
3 Correct 26 ms 18600 KB Output is correct
4 Correct 29 ms 18628 KB Output is correct
5 Correct 14 ms 17616 KB Output is correct
6 Correct 25 ms 21896 KB Output is correct
7 Correct 27 ms 26212 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 7 ms 14420 KB Output is correct
2 Incorrect 7 ms 14420 KB Output isn't correct
3 Halted 0 ms 0 KB -