oj.uz

Submission #283505

# Submission time Handle Problem Language Result Execution time Memory
283505 2020-08-25T21:25:11 Z doowey Magic Tree (CEOI19_magictree) C++14
100 / 100
 989 ms 58484 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<int> T[N];

struct Node{
    ll val;
    ll lazy;
};

Node G[N * 4 + 512];

void push(int node, int cl, int cr){
    G[node].val += G[node].lazy;
    if(cl != cr){
        G[node * 2].lazy += G[node].lazy;
        G[node * 2 + 1].lazy += G[node].lazy;
    }
    G[node].lazy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, ll v){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        G[node].lazy = v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, v);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, v);
    G[node].val = max(G[node * 2].val, G[node * 2 + 1].val);
}

ll get(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return 0ll;
    if(cl >= tl && cr <= tr){
        return G[node].val;
    }
    int mid = (cl + cr) / 2;
    return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
}

int k;

int sub[N];

void dfs(int u){
    sub[u] = 1;
    for(auto x : T[u]){
        dfs(x);
        sub[u] += sub[x];
    }
}

set<int> ff[N];
set<pii> res[N];
int tr[N], ww[N];

struct R{
    int lef;
    int rig;
    ll ch;
};

vector<R> rev[N];

void dfs1(int u, bool keep){
    int id = -1;
    for(auto x : T[u]){
        if(id == -1 || sub[x] > sub[id])
            id = x;
    }
    for(auto x : T[u]){
        if(x != id){
            dfs1(x, false);
            for(auto y : ff[x]){
                ff[u].insert(y);
            }
            ff[x].clear();
        }
    }
    if(id != -1){
        dfs1(id, true);
        swap(ff[u], ff[id]);
        for(auto y : ff[id]){
            ff[u].insert(y);
        }
        ff[id].clear();
        swap(rev[u], rev[id]);
    }
    for(auto x : T[u]){
        if(x != id){
            int las = 0;
            ll cv = -1;
            for(auto y : res[x]){
                if(las != 0){
                    upd(1, 1, k, las, y.fi - 1, cv);
                    rev[u].push_back({las, y.fi - 1, cv});
                }
                las = y.fi;
                cv = y.se;
            }
            if(las != 0){
                upd(1, 1, k, las, k, cv);
                rev[u].push_back({las, k, cv});
            }
        }
    }
    if(tr[u] > 0){
        ff[u].insert(tr[u]);
        auto it = ff[u].find(tr[u]);
        auto nx = it;
        nx ++ ;
        int op, en;
        ll upd_v = get(1, 1, k, tr[u], tr[u]) + ww[u];
        ll cur_v;
        while(1){
            op = *it;
            if(nx == ff[u].end()){
                en = k;
            }
            else{
                en = *nx - 1;
            }
            cur_v = get(1, 1, k, en, en);
            if(cur_v >= upd_v) break;
            upd(1, 1, k, op, en, upd_v - cur_v);
            rev[u].push_back({op, en, upd_v - cur_v});
            if(nx==ff[u].end())
                break;
            nx++;
            it=ff[u].erase(it);
        }
        ff[u].insert(tr[u]);
    }

    if(!keep){
        for(auto x : ff[u]){
            res[u].insert(mp(x, get(1, 1, k, x, x)));
        }
        for(auto f : rev[u]){
            upd(1, 1, k, f.lef, f.rig, -f.ch);
        }
        rev[u].clear();
    }
}


int main(){
    fastIO;
    int n, m;
    cin >> n >> m >> k;
    int p;
    for(int i = 2; i <= n; i ++ ){
        cin >> p;
        T[p].push_back(i);
    }
    int id;
    for(int i = 1; i <= m ; i ++ ){
        cin >> id >> tr[id] >> ww[id];
    }
    dfs(1);
    dfs1(1, true);
    cout << G[1].val;
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14464 KB Output is correct
9 Correct 10 ms 14464 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 33524 KB Output is correct
2 Correct 159 ms 33388 KB Output is correct
3 Correct 868 ms 57876 KB Output is correct
4 Correct 396 ms 38504 KB Output is correct
5 Correct 468 ms 39276 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14720 KB Output is correct
2 Correct 11 ms 14720 KB Output is correct
3 Correct 11 ms 14720 KB Output is correct
4 Correct 237 ms 43876 KB Output is correct
5 Correct 200 ms 44900 KB Output is correct
6 Correct 374 ms 44772 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 25080 KB Output is correct
2 Correct 135 ms 24568 KB Output is correct
3 Correct 101 ms 29808 KB Output is correct
4 Correct 78 ms 27244 KB Output is correct
5 Correct 78 ms 37612 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14464 KB Output is correct
9 Correct 10 ms 14464 KB Output is correct
10 Correct 245 ms 30456 KB Output is correct
11 Correct 207 ms 28668 KB Output is correct
12 Correct 133 ms 28780 KB Output is correct
13 Correct 101 ms 26608 KB Output is correct
14 Correct 104 ms 36588 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17536 KB Output is correct
2 Correct 64 ms 20216 KB Output is correct
3 Correct 74 ms 21604 KB Output is correct
4 Correct 70 ms 21880 KB Output is correct
5 Correct 26 ms 20220 KB Output is correct
6 Correct 58 ms 24604 KB Output is correct
7 Correct 57 ms 28920 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14464 KB Output is correct
9 Correct 10 ms 14464 KB Output is correct
10 Correct 11 ms 14720 KB Output is correct
11 Correct 11 ms 14720 KB Output is correct
12 Correct 11 ms 14720 KB Output is correct
13 Correct 237 ms 43876 KB Output is correct
14 Correct 200 ms 44900 KB Output is correct
15 Correct 374 ms 44772 KB Output is correct
16 Correct 245 ms 30456 KB Output is correct
17 Correct 207 ms 28668 KB Output is correct
18 Correct 133 ms 28780 KB Output is correct
19 Correct 101 ms 26608 KB Output is correct
20 Correct 104 ms 36588 KB Output is correct
21 Correct 115 ms 20680 KB Output is correct
22 Correct 334 ms 33264 KB Output is correct
23 Correct 541 ms 42056 KB Output is correct
24 Correct 989 ms 58484 KB Output is correct
25 Correct 400 ms 37700 KB Output is correct
26 Correct 477 ms 39656 KB Output is correct
27 Correct 435 ms 38628 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 10 ms 14428 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14464 KB Output is correct
9 Correct 10 ms 14464 KB Output is correct
10 Correct 335 ms 33524 KB Output is correct
11 Correct 159 ms 33388 KB Output is correct
12 Correct 868 ms 57876 KB Output is correct
13 Correct 396 ms 38504 KB Output is correct
14 Correct 468 ms 39276 KB Output is correct
15 Correct 11 ms 14720 KB Output is correct
16 Correct 11 ms 14720 KB Output is correct
17 Correct 11 ms 14720 KB Output is correct
18 Correct 237 ms 43876 KB Output is correct
19 Correct 200 ms 44900 KB Output is correct
20 Correct 374 ms 44772 KB Output is correct
21 Correct 156 ms 25080 KB Output is correct
22 Correct 135 ms 24568 KB Output is correct
23 Correct 101 ms 29808 KB Output is correct
24 Correct 78 ms 27244 KB Output is correct
25 Correct 78 ms 37612 KB Output is correct
26 Correct 245 ms 30456 KB Output is correct
27 Correct 207 ms 28668 KB Output is correct
28 Correct 133 ms 28780 KB Output is correct
29 Correct 101 ms 26608 KB Output is correct
30 Correct 104 ms 36588 KB Output is correct
31 Correct 24 ms 17536 KB Output is correct
32 Correct 64 ms 20216 KB Output is correct
33 Correct 74 ms 21604 KB Output is correct
34 Correct 70 ms 21880 KB Output is correct
35 Correct 26 ms 20220 KB Output is correct
36 Correct 58 ms 24604 KB Output is correct
37 Correct 57 ms 28920 KB Output is correct
38 Correct 115 ms 20680 KB Output is correct
39 Correct 334 ms 33264 KB Output is correct
40 Correct 541 ms 42056 KB Output is correct
41 Correct 989 ms 58484 KB Output is correct
42 Correct 400 ms 37700 KB Output is correct
43 Correct 477 ms 39656 KB Output is correct
44 Correct 435 ms 38628 KB Output is correct
45 Correct 106 ms 20584 KB Output is correct
46 Correct 334 ms 33212 KB Output is correct
47 Correct 518 ms 41200 KB Output is correct
48 Correct 920 ms 56812 KB Output is correct
49 Correct 377 ms 38444 KB Output is correct
50 Correct 488 ms 39692 KB Output is correct
51 Correct 424 ms 38500 KB Output is correct