Submission #1232968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232968		Tenis0206	Magic Tree (CEOI19_magictree)	C++20	100 / 100	622 ms	238328 KiB

magictree

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;

int n, m, k;
int t[nmax + 5];
vector<int> G[nmax + 5];

int d[nmax + 5], val[nmax + 5];

int w[nmax + 5], Max[nmax + 5];

vector<pair<pair<int,int>,int>> l;

struct arbore_de_intervale
{
    struct Node
    {
        int Min, Max;
        int lazy_set, lazy_add;
    };

    Node ai[4 * nmax + 5];

    Node Merge(Node a, Node b)
    {
        Node rez;
        rez.Max = max(a.Max, b.Max);
        rez.Min = min(a.Min, b.Min);
        rez.lazy_set = -1;
        rez.lazy_add = 0;
        return rez;
    }

    void propag(int nod)
    {
        if(ai[nod].lazy_add == 0 && ai[nod].lazy_set == -1)
        {
            return;
        }
        if(ai[nod].lazy_set != -1)
        {
            ai[nod * 2].Min = ai[nod * 2 + 1].Min = ai[nod].lazy_set;
            ai[nod * 2].Max = ai[nod * 2 + 1].Max = ai[nod].lazy_set;
            ai[nod * 2].lazy_set = ai[nod * 2 + 1].lazy_set = ai[nod].lazy_set;
            ai[nod * 2].lazy_add = ai[nod * 2 + 1].lazy_add = 0;
            ai[nod].lazy_set = -1;
        }
        else
        {
            ai[nod * 2].Min += ai[nod].lazy_add;
            ai[nod * 2 + 1].Min += ai[nod].lazy_add;

            ai[nod * 2].Max += ai[nod].lazy_add;
            ai[nod * 2 + 1].Max += ai[nod].lazy_add;

            if(ai[nod * 2].lazy_set != -1)
            {
                ai[nod * 2].lazy_set += ai[nod].lazy_add;
                ai[nod * 2].lazy_add = 0;
            }
            else
            {
                ai[nod * 2].lazy_add += ai[nod].lazy_add;
            }

            if(ai[nod * 2 + 1].lazy_set != -1)
            {
                ai[nod * 2 + 1].lazy_set += ai[nod].lazy_add;
                ai[nod * 2 + 1].lazy_add = 0;
            }
            else
            {
                ai[nod * 2 + 1].lazy_add += ai[nod].lazy_add;
            }

            ai[nod].lazy_add = 0;
        }
    }

    void update_set(int ua, int ub, int val, int nod, int a, int b)
    {
        if(ua <= a && ub >= b)
        {
            ai[nod].Min = ai[nod].Max = ai[nod].lazy_set = val;
            ai[nod].lazy_add = 0;
            return;
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(ua <= mij)
        {
            update_set(ua, ub, val, nod * 2, a, mij);
        }
        if(ub > mij)
        {
            update_set(ua, ub, val, nod * 2 + 1, mij + 1, b);
        }
        ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
    }

    void update_add(int ua, int ub, int val, int nod, int a, int b)
    {
        if(ua <= a && ub >= b)
        {
            if(ai[nod].lazy_set != -1)
            {
                ai[nod].lazy_set += val;
                ai[nod].lazy_add = 0;
            }
            else
            {
                ai[nod].lazy_add += val;
            }
            ai[nod].Max += val;
            ai[nod].Min += val;
            return;
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(ua <= mij)
        {
            update_add(ua, ub, val, nod * 2, a, mij);
        }
        if(ub > mij)
        {
            update_add(ua, ub, val, nod * 2 + 1, mij + 1, b);
        }
        ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
    }

    Node query(int qa, int qb, int nod, int a, int b)
    {
        if(qa <= a && qb >= b)
        {
            return ai[nod];
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(qa <= mij && qb > mij)
        {
            return Merge(query(qa, qb, nod * 2, a, mij), query(qa, qb, nod * 2 + 1, mij + 1, b));
        }
        if(qa <= mij)
        {
            return query(qa, qb, nod * 2, a, mij);
        }
        return query(qa, qb, nod * 2 + 1, mij + 1, b);
    }

    void parcurg(int nod, int a, int b)
    {
        if(ai[nod].Max == ai[nod].Min)
        {
            l.push_back({{a, b}, ai[nod].Min});
            return;
        }
        propag(nod);
        int mij = (a + b) >> 1;
        parcurg(nod * 2, a, mij);
        parcurg(nod * 2 + 1, mij + 1, b);
    }

    void init(int nod, int a, int b)
    {
        ai[nod].lazy_set = -1;
        if(a == b)
        {
            return;
        }
        int mij = (a + b) >> 1;
        init(nod * 2, a, mij);
        init(nod * 2 + 1, mij + 1, b);
    }

} ai[25];

void get_w(int nod)
{
    w[nod] = 1;
    Max[nod] = 0;
    for(auto it : G[nod])
    {
        get_w(it);
        w[nod] += w[it];
        if(w[it] > w[Max[nod]])
        {
            Max[nod] = it;
        }
    }
}

void dfs(int nod, int path = 1)
{
    if(G[nod].size() == 0)
    {
        if(d[nod])
        {
            ai[path].update_set(d[nod], k, val[nod], 1, 1, k);
        }
        return;
    }
    dfs(Max[nod], path);
    for(auto it : G[nod])
    {
        if(it == Max[nod])
        {
            continue;
        }
        dfs(it, path + 1);
        l.clear();
        ai[path + 1].parcurg(1, 1, k);
        ai[path + 1].update_set(1, k, 0, 1, 1, k);
        for(auto upd : l)
        {
            ai[path].update_add(upd.first.first, upd.first.second, upd.second, 1, 1, k);
        }
    }
    if(d[nod])
    {
        int val_dp = ai[path].query(d[nod], d[nod], 1, 1, k).Max;
        int st = d[nod];
        int dr = k;
        int poz = 0;
        while(st <= dr)
        {
            int mij = (st + dr) >> 1;
            if(val_dp + val[nod] > ai[path].query(d[nod], mij, 1, 1, k).Max)
            {
                poz = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }
        ai[path].update_set(d[nod], poz, val_dp + val[nod], 1, 1, k);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++)
    {
        cin>>t[i];
        G[t[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        int nod;
        cin>>nod;
        cin>>d[nod]>>val[nod];
    }
    for(int i=1;i<=24;i++)
    {
        ai[i].init(1, 1, k);
    }
    get_w(1);
    dfs(1);
    cout<<ai[1].ai[1].Max<<'\n';
    return 0;
}

• 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