Submission #1173754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173754		sofija6	Magic Tree (CEOI19_magictree)	C++20	3 / 100	58 ms	15944 KiB

magictree

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
using namespace std;
ll n,sz,in[MAXN],out[MAXN],cnt=1,d[MAXN],dp[MAXN];
vector<ll> G[MAXN];
void DFS(ll i)
{
    in[i]=out[i]=cnt++;
    for (ll next : G[i])
    {
        d[next]=d[i]+1;
        DFS(next);
        out[i]=max(out[i],out[next]);
    }
}
struct seg_tree
{
    vector<ll> st;
    void Init()
    {
        sz=1;
        while (sz<n)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Add(ll pos,ll val,ll x,ll lx,ll rx)
    {
        if (lx==rx)
        {
            st[x]+=val;
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Add(pos,val,2*x,lx,mid);
        else
            Add(pos,val,2*x+1,mid+1,rx);
        st[x]=st[2*x]+st[2*x+1];
    }
    ll Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return 0;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Calc(l,r,2*x,lx,mid)+Calc(l,r,2*x+1,mid+1,rx);
    }
};
seg_tree S;
vector<pair<ll,ll> > f[MAXN];
bool Cmp(pair<ll,ll> a,pair<ll,ll> b)
{
    return d[a.first]>d[b.first];
}
void DFS_Solve(ll i)
{
    ll sum=0;
    for (ll next : G[i])
    {
        DFS_Solve(next);
        sum+=dp[next];
    }
    dp[i]=max(dp[i],sum);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll m,k,p,v,d,w,ans=0;
    cin >> n >> m >> k;
    for (ll i=2;i<=n;i++)
    {
        cin >> p;
        G[p].push_back(i);
    }
    for (ll i=1;i<=m;i++)
    {
        cin >> v >> d >> w;
        f[d].push_back({v,w});
    }
    DFS(1);
    S.Init();
    for (ll i=1;i<=k;i++)
    {
        sort(f[i].begin(),f[i].end(),Cmp);
        for (auto j : f[i])
        {
            v=j.first;
            w=j.second;
            S.Add(in[v],w,1,1,sz);
            dp[v]=S.Calc(in[v],out[v],1,1,sz);
        }
    }
    DFS_Solve(1);
    cout << dp[1];
    return 0;
}

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