oj.uz

Submission #798166

# Submission time Handle Problem Language Result Execution time Memory
798166 2023-07-30T12:27:19 Z Ronin13 Magic Tree (CEOI19_magictree) C++17
100 / 100
 857 ms 213408 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 79696 KB Output is correct
2 Correct 132 ms 43760 KB Output is correct
3 Correct 734 ms 207824 KB Output is correct
4 Correct 309 ms 101448 KB Output is correct
5 Correct 399 ms 103308 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7636 KB Output is correct
2 Correct 5 ms 7628 KB Output is correct
3 Correct 4 ms 7636 KB Output is correct
4 Correct 188 ms 43836 KB Output is correct
5 Correct 171 ms 43828 KB Output is correct
6 Correct 235 ms 43780 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 21400 KB Output is correct
2 Correct 102 ms 17944 KB Output is correct
3 Correct 106 ms 24452 KB Output is correct
4 Correct 94 ms 24976 KB Output is correct
5 Correct 100 ms 33652 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 194 ms 40016 KB Output is correct
11 Correct 140 ms 32908 KB Output is correct
12 Correct 101 ms 26616 KB Output is correct
13 Correct 106 ms 38604 KB Output is correct
14 Correct 88 ms 33100 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10544 KB Output is correct
2 Correct 44 ms 15892 KB Output is correct
3 Correct 45 ms 15864 KB Output is correct
4 Correct 45 ms 16540 KB Output is correct
5 Correct 23 ms 16152 KB Output is correct
6 Correct 44 ms 19240 KB Output is correct
7 Correct 42 ms 22004 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 5 ms 7636 KB Output is correct
11 Correct 5 ms 7628 KB Output is correct
12 Correct 4 ms 7636 KB Output is correct
13 Correct 188 ms 43836 KB Output is correct
14 Correct 171 ms 43828 KB Output is correct
15 Correct 235 ms 43780 KB Output is correct
16 Correct 194 ms 40016 KB Output is correct
17 Correct 140 ms 32908 KB Output is correct
18 Correct 101 ms 26616 KB Output is correct
19 Correct 106 ms 38604 KB Output is correct
20 Correct 88 ms 33100 KB Output is correct
21 Correct 94 ms 28260 KB Output is correct
22 Correct 279 ms 69784 KB Output is correct
23 Correct 448 ms 124092 KB Output is correct
24 Correct 759 ms 212064 KB Output is correct
25 Correct 296 ms 100804 KB Output is correct
26 Correct 369 ms 81016 KB Output is correct
27 Correct 275 ms 54248 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 3 ms 7252 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 260 ms 79696 KB Output is correct
11 Correct 132 ms 43760 KB Output is correct
12 Correct 734 ms 207824 KB Output is correct
13 Correct 309 ms 101448 KB Output is correct
14 Correct 399 ms 103308 KB Output is correct
15 Correct 5 ms 7636 KB Output is correct
16 Correct 5 ms 7628 KB Output is correct
17 Correct 4 ms 7636 KB Output is correct
18 Correct 188 ms 43836 KB Output is correct
19 Correct 171 ms 43828 KB Output is correct
20 Correct 235 ms 43780 KB Output is correct
21 Correct 123 ms 21400 KB Output is correct
22 Correct 102 ms 17944 KB Output is correct
23 Correct 106 ms 24452 KB Output is correct
24 Correct 94 ms 24976 KB Output is correct
25 Correct 100 ms 33652 KB Output is correct
26 Correct 194 ms 40016 KB Output is correct
27 Correct 140 ms 32908 KB Output is correct
28 Correct 101 ms 26616 KB Output is correct
29 Correct 106 ms 38604 KB Output is correct
30 Correct 88 ms 33100 KB Output is correct
31 Correct 16 ms 10544 KB Output is correct
32 Correct 44 ms 15892 KB Output is correct
33 Correct 45 ms 15864 KB Output is correct
34 Correct 45 ms 16540 KB Output is correct
35 Correct 23 ms 16152 KB Output is correct
36 Correct 44 ms 19240 KB Output is correct
37 Correct 42 ms 22004 KB Output is correct
38 Correct 94 ms 28260 KB Output is correct
39 Correct 279 ms 69784 KB Output is correct
40 Correct 448 ms 124092 KB Output is correct
41 Correct 759 ms 212064 KB Output is correct
42 Correct 296 ms 100804 KB Output is correct
43 Correct 369 ms 81016 KB Output is correct
44 Correct 275 ms 54248 KB Output is correct
45 Correct 105 ms 28444 KB Output is correct
46 Correct 281 ms 70160 KB Output is correct
47 Correct 505 ms 123196 KB Output is correct
48 Correct 857 ms 213408 KB Output is correct
49 Correct 329 ms 101516 KB Output is correct
50 Correct 350 ms 81816 KB Output is correct
51 Correct 314 ms 54992 KB Output is correct