Submission #798166

#	Time	Username	Problem	Language	Result	Execution time	Memory
798166		Ronin13	Magic Tree (CEOI19_magictree)	C++17	100 / 100	857 ms	213408 KiB

magictree

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <bitset>
 
#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
 
using namespace std;
 
struct node{
    node *l, *r;
    ll lazy, mx;
    node(){
        l = r = NULL;
        lazy = mx = 0;
    }
    node(node *l, node *r) : l(l), r(r){
        mx = 0, lazy =0;
        if(l != NULL) mx = max(mx, l->mx);
        if(r != NULL) mx = max(mx, r->mx);
    }
};
 
void push(node *v){
    if(v->l != NULL) v->l->mx += v->lazy, v->l->lazy += v->lazy;
    if(v->r != NULL) v->r->mx += v->lazy, v->r->lazy += v->lazy;
    v->lazy = 0;
}
 
void update(node *v, int l, int r, int st, int fin, ll val){
    if(l > fin || r < st || v == NULL){
        return;
    }
    if(l >= st && r <= fin){
        v->mx += val, v->lazy += val; return;
    }
    push(v);
    int m = (l + r) / 2;
    update(v->l, l, m, st, fin, val);
    update(v->r, m + 1, r, st, fin, val);
    v->mx = 0;
    if(v->l) v->mx = max(v->mx, v->l->mx);
    if(v->r) v->mx = max(v->mx, v->r->mx);
}
 
node *update_p(node *v, int l, int r, int pos, ll val){
    if(v == NULL) v = new node();
    if(l == r){
       // cout << val << ' ';
        v->mx = max(v->mx, val);v->lazy = 0; return v;
    }
    int m = (l + r) / 2;
    push(v);
    if(pos <= m) {
        node *x = update_p(v->l, l, m, pos, val);
        node *y = v->r;
        node *z = new node(x, y);
        swap(z, v);
        delete(z);
        //cout << v->mx;
        return v;
    }
    if(pos > m){
        node *x = v->l;
        node *y = update_p(v->r, m + 1, r, pos, val);
        node *z = new node(x, y);
        swap(z, v);
        delete(z);
        //cout << v->mx;
        return v;
    }
}
 
ll get(node *v, int l, int r, int st, int fin){
    if(l > fin || r < st || v == NULL){
        return 0;
    }
    if(l >= st && r <= fin){
        return v->mx;
    }
    int m = (l + r) / 2;
    push(v);
    return max(get(v->r, m + 1, r, st, fin), 
                get(v->l, l, m, st, fin));
}
const int nmax = 100001;
node *root[nmax];
set <int> st[nmax];
ll d[nmax], w[nmax]; 
vector <vector <int> > g(nmax);
int k;
void dfs(int v, int e){
    //cout << d[v] << ' ' << w[v] << "\n";
   // cout << v << ' ';
    int mxi = -1, mx = -1;
    for(int i = 0; i < g[v].size(); ++i){
        int to = g[v][i];
        if(to == e) continue;
        dfs(to, v);
        //cout << mx << "\n";
        if((int)mx < (int)st[to].size()) mx = (int)st[to].size(), mxi = to;
    }
   // cout << v << ' ' << mx << "\n";
    if(mxi == -1){
        root[v] = new node();
        if(w[v]) root[v] = update_p(root[v], 1, k, d[v], w[v]), st[v].insert(d[v]);
     //   cout << root[v]->mx << "\n";
        return;
    }
    
    root[v] = root[mxi];
    swap(st[v], st[mxi]);
    for(int i = 0; i < g[v].size(); ++i){
        int to = g[v][i];
        if(to == e || to == mxi) continue;
        int lst = -1;
        ll lstans;
        for(set <int> :: reverse_iterator it = st[to].rbegin(); it != st[to].rend(); it++){
            int x = *it;
            ll val = get(root[to], 1, k, 1, x) + get(root[v], 1, k, 1, x);
            root[v] = update_p(root[v], 1,k, x, val); 
        }
        for(set <int>:: iterator it = st[to].begin(); it != st[to].end(); it++){
            int x = *it; 
            if(lst != -1 && lst + 1 <= x - 1){
                update(root[v], 1, k, lst + 1 ,x - 1, lstans);
            }
            lst = x;
            lstans = get(root[to], 1, k, 1, x);
          //  ll o = get(root[v], 1, k, 1, x) + lstans;
          //  root[v] = update_p(root[v], 1, k, x, o);
            st[v].insert(x);
        }
        if(lst != -1)update(root[v], 1, k, lst + 1, k, lstans);
    }
    
    if(w[v]){
        ll ans = get(root[v], 1, k, 1, d[v]);
        root[v] = update_p(root[v], 1, k, d[v], ans + w[v]);
        st[v].insert(d[v]);
    }
 //  cout << root[v]->mx << "\n";
}
 
int main(){
    int n; cin >>n;
    int m; cin >> m;
    cin >> k;
    for(int i = 2; i <= n; i++){
        int p; cin >> p;
        g[p].pb(i);
    }
    for(int i = 1; i <= m; i++){
        int v; cin >> v;
        cin >> d[v] >> w[v];
    }
    dfs(1, 1);
    cout << root[1]->mx;
    return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int, int)':
magictree.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < g[v].size(); ++i){
      |                    ~~^~~~~~~~~~~~~
magictree.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = 0; i < g[v].size(); ++i){
      |                    ~~^~~~~~~~~~~~~
magictree.cpp: In function 'node* update_p(node*, int, int, int, long long int)':
magictree.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

• 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