oj.uz

Submission #418328

# Submission time Handle Problem Language Result Execution time Memory
418328 2021-06-05T09:55:24 Z ACmachine Magic Tree (CEOI19_magictree) C++17
17 / 100
 292 ms 31960 KB 
#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);
}
treap* normalizeutil(treap *t, ll val){
    if(t == NULL)
        return NULL;
    push(t);
    if(t->val <= val){
        return normalizeutil(t->ch[1], val);
    }
    t->ch[0] = normalizeutil(t->ch[0], val);
    recalc(t);
    return t;
}
treap* normalize(treap *t, ll val){
    if(t == NULL)
        return NULL;
    if(t->maxi <= val) 
        return NULL;
    return normalizeutil(t, val); 
}
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);
    }
    array<ll, 2> nl = {-1, -1};
    vector<array<ll, 2>> fruits(n, nl);
    REP(i, m){
        int v, d, w;
        cin >> v >> d >> w;
        v--;
        fruits[v] = {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 fruit   
        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 fruit
        if(fruits[v] != nl){
            ll val = -1;
            auto x = fruits[v];
            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]);
            auto pa = split(dp[v], x[0] + 1);
            pa.ss = normalize(pa.ss, val + x[1]);
            dp[v] = merge(pa.ff, pa.ss);
        } 
        //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

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:158:5: note: in expansion of macro 'REP'
  158 |     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:193:9: note: in expansion of macro 'FOR'
  193 |         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:201:9: note: in expansion of macro 'FOR'
  201 |         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:214:13: note: in expansion of macro 'REP'
  214 |             REP(j, tv.size()){
      |             ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 13028 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 92 ms 29612 KB Output is correct
5 Correct 143 ms 29644 KB Output is correct
6 Correct 292 ms 31960 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 10768 KB Output is correct
2 Correct 94 ms 11596 KB Output is correct
3 Correct 90 ms 17036 KB Output is correct
4 Runtime error 45 ms 12736 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 183 ms 16964 KB Output is correct
11 Correct 162 ms 15536 KB Output is correct
12 Correct 100 ms 16556 KB Output is correct
13 Runtime error 51 ms 12160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 3136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 92 ms 29612 KB Output is correct
14 Correct 143 ms 29644 KB Output is correct
15 Correct 292 ms 31960 KB Output is correct
16 Correct 183 ms 16964 KB Output is correct
17 Correct 162 ms 15536 KB Output is correct
18 Correct 100 ms 16556 KB Output is correct
19 Runtime error 51 ms 12160 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Runtime error 45 ms 13028 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -