Submission #418293

#	Time	Username	Problem	Language	Result	Execution time	Memory
418293		ACmachine	Magic Tree (CEOI19_magictree)	C++17	0 / 100	124 ms	23796 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
const ll INFF = (ll)1e18;
const int INF = (int)1e9;
mt19937 rng(time(NULL));
// increase on interval;
// get key
// basically like dynamic segtree, but with O(n) memory
struct treap{
    int y;
    int key;
    ll val, lazy;
    ll maxi;
    int cnt = 1;
    array<treap*, 2> ch;
    treap(int _key, ll _val){
        key = _key;
        val = _val; 
        y = rng();
        maxi = val;
        lazy = 0; 
    }
};
int getcnt(treap* t){
    if(t == NULL) return 0;
    else return t->cnt;
}
void recalc(treap *t){
    if(t == NULL) 
        return;
    t->cnt = 1;
    t->maxi = t->val;
    REP(i, 2){
        if(t->ch[i] != NULL){
            t->maxi = max(t->maxi, t->ch[i]->maxi);
        }
        t->cnt += getcnt(t->ch[i]); 
    }
}
void push(treap *t){
    if(t == NULL || t->lazy == 0) 
        return;
    REP(i, 2){
        if(t->ch[i] != NULL){
            t->ch[i]->val += t->lazy;
            t->ch[i]->lazy += t->lazy;
            t->ch[i]->maxi += t->lazy;
        }
    }
    t->lazy = 0;
}
pair<treap*, treap*> split(treap* t, int k){ // all < k goes left
    if(t == NULL)
        return {NULL, NULL};
    push(t);
    if(t->key < k){
        auto pa = split(t->ch[1], k);
        t->ch[1] = pa.ff;
        recalc(t);
        return {t, pa.ss};
    }
    else{
        auto pa = split(t->ch[0], k);
        t->ch[0] = pa.ss;
        recalc(t);
        return {pa.ff, t};
    }
}
treap* merge(treap* f, treap* s){
    if(f == NULL) return s;
    if(s == NULL) return f; 
    if(f->y >= s->y){
        push(f);
        f->ch[1] = merge(f->ch[1], s);
        recalc(f);
        return f;
    }
    else{
        push(s);
        s->ch[0] = merge(f, s->ch[0]);
        recalc(s);
        return s;
    }
}
treap* add_range(treap *t, int l, int r, ll val){ // all with k >= l && k < r add val
    auto pa = split(t, l);
    auto pa2 = split(pa.ss, r);
    if(pa2.ff != NULL){
        pa2.ff->val += val;
        pa2.ff->lazy += val;
        pa2.ff->maxi += val;
    }
    pa.ss = merge(pa2.ff, pa2.ss);
    treap* res = merge(pa.ff, pa.ss);
    return res;
}
treap* get_prev_key(treap *t, int k, ll &val){
    auto pa = split(t, k);
    if(pa.ff != NULL)
        val = pa.ff->maxi;
    return merge(pa.ff, pa.ss);
}
treap* get_key(treap* t, int k, ll &val){
    auto pa = split(t, k);
    auto pa2 = split(pa.ss, k + 1);
    if(pa2.ff != NULL) 
        val = pa2.ff->val;
    pa.ss = merge(pa2.ff, pa2.ss);
    return merge(pa.ff, pa.ss);
}
treap* insert(treap* t, treap *nv){
    if(t == NULL) return nv;
    ll val = -1;
    t = get_key(t, nv->key, val);
    if(val != -1)
        return t;
    auto pa = split(t, nv->key);
    pa.ff = merge(pa.ff, nv);
    return merge(pa.ff, pa.ss);
}
void traverse(treap *t, vector<array<ll, 2>> &v){
    if(t == NULL)
        return;
    push(t);
    traverse(t->ch[0], v); 
    v.pb({t->key, t->val});
    traverse(t->ch[1], v);
}
void print(treap *t){
    vector<array<ll, 2>> els;
    traverse(t, els);
    REP(i, els.size()){
        cout << "[" << els[i][0] << " " << els[i][1] << "], ";
    }
    cout << "\n";
}
vector<array<ll, 2>> get(treap *t){
    vector<array<ll, 2>> els;
    traverse(t, els);
    return els; 
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> g(n);
    FOR(i, 1, n, 1){
        int p;
        cin >> p;
        p--;
        g[p].pb(i);
    }
    vector<set<array<ll, 2>>> fruits(n);
    REP(i, m){
        int v, d, w;
        cin >> v >> d >> w;
        v--;
        auto it = fruits[v].lower_bound({d, -INF});
        if(it != fruits[v].end() && (*it)[0] == d){
            ll nw = (*it)[1] + w;
            fruits[v].erase(it);
            fruits[v].insert({d, nw});
        }
        else{
            fruits[v].insert({d, w});
        }
    }
    vector<treap*> dp(n, NULL);
    function<void(int)> dfs = [&](int v){
        for(int x : g[v]){
            dfs(x);
        }
        FOR(i, 1, g[v].size(), 1){
            if(getcnt(dp[g[v][i]]) > getcnt(dp[g[v][0]])){
                swap(g[v][i], g[v][0]);
                swap(dp[g[v][i]], dp[g[v][0]]);
            }
        }
        if(g[v].size() > 0)
            swap(dp[v], dp[g[v][0]]); // first merge children, then current fruits   
        FOR(i, 1, g[v].size(), 1){
            vector<array<ll, 2>> tv; // traversal
            traverse(dp[g[v][i]], tv);
            for(auto x : tv){
                ll val = -1;
                dp[v] = get_key(dp[v], x[0], val);
                if(val == -1){
                    val = 0;
                    dp[v] = get_prev_key(dp[v], x[0], val);
                    dp[v] = insert(dp[v], new treap(x[0], val));
                }
            }
            ll maxi = 0;
            REP(j, tv.size()){
                if(j != 0){
                    dp[v] = add_range(dp[v], tv[j - 1][0], tv[j][0], maxi);
                }
                maxi = max(maxi, tv[j][1]);
            }
            if(tv.size() > 0) {
                dp[v] = add_range(dp[v], tv.back()[0], INF + 5, maxi);
            }
        }
        // merge current fruits
        vector<array<ll, 2>> tv; // traversal
        for(auto x : fruits[v]){
            tv.pb(x);
        }
        reverse(tv.begin(), tv.end());
        for(auto x : tv){
            ll val = -1;
            dp[v] = get_key(dp[v], x[0], val);
            if(val == -1){
                val = 0;
                dp[v] = get_prev_key(dp[v], x[0], val);
                dp[v] = insert(dp[v], new treap(x[0], val));
            }
            dp[v] = add_range(dp[v], x[0], x[0] + 1, x[1]);
        } 
        //cout << v << " ";
        //print(dp[v]);
    };
    dfs(0);
    ll ans = 0;
    dp[0] = get_prev_key(dp[0], INF + 10, ans);
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void print(treap*)':
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
magictree.cpp:5:19: note: in expansion of macro 'FOR'
    5 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
magictree.cpp:140:5: note: in expansion of macro 'REP'
  140 |     REP(i, els.size()){
      |     ^~~
magictree.cpp: In lambda function:
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
magictree.cpp:182:9: note: in expansion of macro 'FOR'
  182 |         FOR(i, 1, g[v].size(), 1){
      |         ^~~
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
magictree.cpp:190:9: note: in expansion of macro 'FOR'
  190 |         FOR(i, 1, g[v].size(), 1){
      |         ^~~
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
magictree.cpp:5:19: note: in expansion of macro 'FOR'
    5 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
magictree.cpp:203:13: note: in expansion of macro 'REP'
  203 |             REP(j, tv.size()){
      |             ^~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 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