Submission #1135389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135389		Zbyszek99	Magic Tree (CEOI19_magictree)	C++20	100 / 100	478 ms	355396 KiB

magictree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int tree_siz = (1<<17);

struct node
{
    int l = 0;
    int r = tree_siz-1;
    bool is_right = 0;
    bool is_left = 0;
    ll sum = 0;
    node* left;
    node* right;
    void get_left()
    {
        if(is_left) return;
        is_left = true;
        left = new node;
        left -> l = l;
        left -> r = (l+r)/2;
    }
    void get_right()
    {
        if(is_right) return;
        is_right = true;
        right = new node;
        right -> l = (l+r)/2+1;
        right -> r = r;
    }
    ll get_val(int ind)
    {
        ll ans = sum;
        if(l == r) return ans;
        if(ind <= (l+r)/2)
        {
            get_left();
            ans += left -> get_val(ind);
        }
        else
        {
            get_right();
            ans += right -> get_val(ind);
        }
        return ans;
    }
    void add_seg(int p1, int p2, ll w)
    {
       // cout << l << " " << r << " add\n";
        if(r < p1 || l > p2) return;
        if(l >= p1 && r <= p2)
        {
            sum += w;
            return;
        }
        get_left();
        get_right();
        left -> add_seg(p1,p2,w);
        right -> add_seg(p1,p2,w);
    }
};

struct dp_str
{
    set<int> poz_dp;
    node dp;
    void merge(dp_str& d)
    {
        ll pop_val = 0;
        forall(it,d.poz_dp)
        {
            if(poz_dp.find(it) == poz_dp.end())
            {
                poz_dp.insert(it);
            }
            ll val = d.dp.get_val(it);
            dp.add_seg(it,tree_siz-1,val-pop_val);
            pop_val = val;
        }
    }
    void max_with(int ind, ll w)
    {
        if(poz_dp.find(ind) == poz_dp.end())
        {
            poz_dp.insert(ind);
        }
        ll cur_val = dp.get_val(ind);
        auto it = poz_dp.upper_bound(ind);
        if(it == poz_dp.end())
        {
           // cout << "xd\n";
            dp.add_seg(ind,tree_siz-1,w);
            return;
        }
        else
        {
            dp.add_seg(ind,(*it)-1,-cur_val);
        }
        ll dp_val = dp.get_val(*it);
        while(it != poz_dp.end() && dp_val < cur_val+w)
        {
            int pop_poz = *it;
            poz_dp.erase(it);
            it = poz_dp.upper_bound(ind);
            if(it != poz_dp.end())
            {
                dp.add_seg(pop_poz,(*it)-1,-dp_val);
                dp_val = dp.get_val(*it);
            }
            else
            {
                dp.add_seg(pop_poz,tree_siz-1,-dp_val);
            }
        }
        if(it != poz_dp.end())
        {
            dp.add_seg(ind,(*it)-1,cur_val+w);
        }
        else
        {
            dp.add_seg(ind,tree_siz-1,cur_val+w);
        }
    }
};

dp_str dps[100001];
vi graph[100001];
pll magic[100001];

void dfs(int v)
{
    forall(it,graph[v])
    {
        dfs(it);
        if(siz(dps[it].poz_dp) > siz(dps[v].poz_dp)) swap(dps[it],dps[v]);
        dps[v].merge(dps[it]); 
    }
    if(magic[v].ff != -1)
    {
        dps[v].max_with(magic[v].ff,magic[v].ss);
    }
   // cout << v << " dfs\n";
   // forall(it,dps[v].poz_dp)
   // {
   //     cout << it << " " << dps[v].dp.get_val(it) << " dp\n";
   // }
   // cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m,k;
    cin >> n >> m >> k;
    rep2(i,2,n)
    {
        int p;
        cin >> p;
        graph[p].pb(i);
    }
    rep2(i,1,n) magic[i] = {-1,-1};
    rep(i,m)
    {
        int v,d;
        ll w;
        cin >> v >> d >> w;
        magic[v] = {d,w};
    }
    dfs(1);
    cout << dps[1].dp.get_val(k);
}

• 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