Submission #909288

#	Time	Username	Problem	Language	Result	Execution time	Memory
909288		ibm2006	Magic Tree (CEOI19_magictree)	C++17	100 / 100	156 ms	65936 KiB

magictree

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,b[1100000],h[1100000],m;
vector<ll> v[1100000],u;
pair<ll,ll> a[1100000];
multiset<pair<ll,ll>> dp[110000];
void f(ll x,ll y)
{
    ll i,j;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        f(v[x][i],x);
    }
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        if(dp[x].empty())
        {
            swap(dp[x],dp[v[x][i]]);
            continue;
        }
        if(dp[x].size()<dp[v[x][i]].size())
            swap(dp[x],dp[v[x][i]]);
        for(pair<ll,ll> p:dp[v[x][i]])
        {
            dp[x].insert(p);
        }
        dp[v[x][i]].clear();
    }
    if(a[x].first==0)
        return;
    dp[x].insert({a[x].first,a[x].second});
    pair<ll,ll> p;
    p={a[x].first+1,0};
    s=0;
    pair<ll,ll> id;
    while(1)
    {
        if(dp[x].lower_bound(p)==dp[x].end())
            break;
        id=(*dp[x].lower_bound(p));
        if(id.second+s>=a[x].second)
        {
            dp[x].erase(dp[x].find(id));
            dp[x].insert({id.first,id.second+s-a[x].second});
            break;
        }
        dp[x].erase(dp[x].find(id));
        s+=id.second;
    }
}
int main()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    for(i=2;i<=n;i++)
    {
        scanf("%lld",&x);
        y=i;
        v[x].push_back(y);
        v[y].push_back(x);
        h[x]++;
        h[y]++;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        a[x]={y,z};
    }
    f(1,0);
    s=0;
    for(pair<ll,ll> p:dp[1])
    {
        s+=p.second;
    }
    printf("%lld",s);
}

Compilation message (stderr)

magictree.cpp: In function 'void f(ll, ll)':
magictree.cpp:10:10: warning: unused variable 'j' [-Wunused-variable]
   10 |     ll i,j;
      |          ^
magictree.cpp: In function 'int main()':
magictree.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld %lld %lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld",&x);
      |         ~~~~~^~~~~~~~~~~
magictree.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17