oj.uz

Submission #570006

# Submission time Handle Problem Language Result Execution time Memory
570006 2022-05-28T12:31:26 Z Redhood Magic Tree (CEOI19_magictree) C++14
100 / 100
 431 ms 36136 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;

using namespace std;


const int N = (int)1e5 + 10;
const ll inf = 1e18;
struct node{
    ll eq=-1;
    ll add;
    ll pushmx;
    node(){
        eq = 0;
        add = 0;
        pushmx = 0;
    }
};
node seg[4*N];

void push(int v){
    int v1 = v << 1;
    for(auto &u : {v1 , v1|1}){
        if(seg[v].eq != -1){
            seg[u].eq=seg[v].eq,seg[u].add=0,seg[u].pushmx=seg[v].pushmx;
        }else{
            if(seg[u].eq!=-1)
                seg[u].eq+=seg[v].add,seg[u].pushmx+=seg[v].add;
            else{
                seg[u].add+=seg[v].add;
                seg[u].pushmx+=seg[v].add;
            }
            seg[u].pushmx=max(seg[u].pushmx,seg[v].pushmx);
        }
    }
    seg[v].eq = -1;
    seg[v].add = 0;
    seg[v].pushmx = 0;
}

void doadd(int v , int tl , int tr , int l , int r , ll x){
    if(tl == l && tr == r){
        if(seg[v].eq!=-1){
            seg[v].eq += x;
        }else
            seg[v].add += x;
        seg[v].pushmx += x;
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1, v1 = v << 1;
    if(l <= mid)
        doadd(v1 , tl , mid , l , min(r , mid) , x);
    if(r > mid)
        doadd(v1|1, mid + 1 , tr , max(l , mid + 1) , r , x);
//    pull(v);
}
ll get(int v , int tl , int tr , int pos){
    if(tl == tr){
        return seg[v].pushmx;
    }
    push(v);
    int mid = (tl + tr) >> 1, v1 = v << 1;
    if(pos <= mid)
        return get(v1, tl , mid , pos);
    return get(v1|1,mid+1,tr,pos);
}
void domx(int v , int tl, int tr , int l , int r , ll x){
    if(tl == l && tr == r){
        seg[v].pushmx = max(seg[v].pushmx , x);
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1 , v1 = v << 1;
    if(l <= mid)
        domx(v1 , tl , mid , l , min(r , mid) , x);
    if(r > mid)
        domx(v1|1,mid+1,tr,max(l,mid+1),r,x);
}
vector < int > g[N];
int ripeday[N], w[N];
vector < int > *vert[N];
vector<pair<int,ll>>temp[N];
int sz[N];
void sizes(int v){
    sz[v] = 1;
    for(auto &u : g[v]){
        sizes(u);
        sz[v] += sz[u];
    }
}
void gozero(){
    seg[1].eq = 0;
    seg[1].add=0,seg[1].pushmx=0;
}
void dfs(int v){
//    cerr << v << ' ' << endl;
    int big = -1;
    for(auto &u : g[v]){
        if(big == -1 || sz[u] > sz[big])
            big = u;
    }
    for(auto &u : g[v]){
        if(u != big){
            /// what do we do man?
            dfs(u);
            /// okay now
            if(vert[u]!=nullptr){
                for(auto &d : (*vert[u])){
                    ll x = get(1,0,N-1,d);
                    temp[u].push_back({d , x});
                }
            }
            gozero();
        }
    }
    if(big == -1){
        if(ripeday[v] != -1){
            doadd(1,0,N-1, ripeday[v], N-1, w[v]);
            vert[v] = new vector<int>;
            (*vert[v]).push_back(ripeday[v]);
        }
    }else{
        dfs(big);
        vert[v] = vert[big];
        if(vert[v] == nullptr)
            vert[v] = new vector < int >;
        for(auto &u : g[v]){
            if(u != big){
                if(temp[u].empty())continue;
                sort(all(temp[u]));
                temp[u].erase(unique(all(temp[u])) , temp[u].end());
                int prv = -1;
                for(int i = 0; i < sz(temp[u]); ++i){
                    if(i - 1 >= 0){
//                        assert(temp[u][i-1].se <= temp[u][i].se);
//                        assert(temp[u][i-1].fi != temp[u][i].fi);
                    }
                    int rb = (i == sz(temp[u]) - 1 ? N-1 : temp[u][i + 1].fi - 1);
                    doadd(1 , 0 , N - 1, temp[u][i].fi, rb, temp[u][i].se);
                }
                temp[u].clear();
                for(auto &x : (*vert[u]))
                    (*vert[v]).push_back(x);
            }
        }
        if(ripeday[v] != -1){
            ll t = get(1 , 0 , N - 1 , ripeday[v]);
            t += w[v];
            domx(1 , 0 , N -1 , ripeday[v], N - 1 , t);
            (*vert[v]).push_back(ripeday[v]);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0) , cout.tie(0);
    int n , m, k;
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int p;cin >> p, --p;
        g[p].pb(i);
    }
    fill(ripeday , ripeday + N , -1);
    for(int i = 0; i < m; ++i){
        int v , d;
        cin >> v >> d;
        --v;
        cin >> w[v];
        ripeday[v] = d;
    }
    sizes(0);
    dfs(0);
    ll ans = 0;
    for(int t=0;t<N-1;++t){
        ans = max(ans , get(1 , 0 , N - 1, t));
    }
    cout << ans;

    return 0;
}
/*
5 1 1
1 2 1 1
2 3 1

*/

Compilation message

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:141:21: warning: unused variable 'prv' [-Wunused-variable]
  141 |                 int prv = -1;
      |                     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14804 KB Output is correct
2 Correct 38 ms 14792 KB Output is correct
3 Correct 29 ms 14804 KB Output is correct
4 Correct 27 ms 14804 KB Output is correct
5 Correct 28 ms 14812 KB Output is correct
6 Correct 27 ms 14700 KB Output is correct
7 Correct 36 ms 14804 KB Output is correct
8 Correct 27 ms 14804 KB Output is correct
9 Correct 25 ms 14808 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 22896 KB Output is correct
2 Correct 114 ms 27452 KB Output is correct
3 Correct 370 ms 34752 KB Output is correct
4 Correct 153 ms 28008 KB Output is correct
5 Correct 200 ms 29868 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15008 KB Output is correct
2 Correct 26 ms 14924 KB Output is correct
3 Correct 29 ms 14940 KB Output is correct
4 Correct 116 ms 34104 KB Output is correct
5 Correct 111 ms 33988 KB Output is correct
6 Correct 124 ms 34096 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 30804 KB Output is correct
2 Correct 224 ms 32932 KB Output is correct
3 Correct 141 ms 30088 KB Output is correct
4 Correct 136 ms 27724 KB Output is correct
5 Correct 108 ms 36136 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14804 KB Output is correct
2 Correct 38 ms 14792 KB Output is correct
3 Correct 29 ms 14804 KB Output is correct
4 Correct 27 ms 14804 KB Output is correct
5 Correct 28 ms 14812 KB Output is correct
6 Correct 27 ms 14700 KB Output is correct
7 Correct 36 ms 14804 KB Output is correct
8 Correct 27 ms 14804 KB Output is correct
9 Correct 25 ms 14808 KB Output is correct
10 Correct 291 ms 32164 KB Output is correct
11 Correct 246 ms 32276 KB Output is correct
12 Correct 128 ms 29372 KB Output is correct
13 Correct 120 ms 27096 KB Output is correct
14 Correct 110 ms 35548 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15588 KB Output is correct
2 Correct 57 ms 19300 KB Output is correct
3 Correct 56 ms 19296 KB Output is correct
4 Correct 60 ms 19364 KB Output is correct
5 Correct 39 ms 17108 KB Output is correct
6 Correct 51 ms 21076 KB Output is correct
7 Correct 55 ms 25120 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14804 KB Output is correct
2 Correct 38 ms 14792 KB Output is correct
3 Correct 29 ms 14804 KB Output is correct
4 Correct 27 ms 14804 KB Output is correct
5 Correct 28 ms 14812 KB Output is correct
6 Correct 27 ms 14700 KB Output is correct
7 Correct 36 ms 14804 KB Output is correct
8 Correct 27 ms 14804 KB Output is correct
9 Correct 25 ms 14808 KB Output is correct
10 Correct 27 ms 15008 KB Output is correct
11 Correct 26 ms 14924 KB Output is correct
12 Correct 29 ms 14940 KB Output is correct
13 Correct 116 ms 34104 KB Output is correct
14 Correct 111 ms 33988 KB Output is correct
15 Correct 124 ms 34096 KB Output is correct
16 Correct 291 ms 32164 KB Output is correct
17 Correct 246 ms 32276 KB Output is correct
18 Correct 128 ms 29372 KB Output is correct
19 Correct 120 ms 27096 KB Output is correct
20 Correct 110 ms 35548 KB Output is correct
21 Correct 77 ms 18036 KB Output is correct
22 Correct 205 ms 26380 KB Output is correct
23 Correct 262 ms 26648 KB Output is correct
24 Correct 431 ms 32548 KB Output is correct
25 Correct 139 ms 27324 KB Output is correct
26 Correct 220 ms 29088 KB Output is correct
27 Correct 166 ms 29708 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14804 KB Output is correct
2 Correct 38 ms 14792 KB Output is correct
3 Correct 29 ms 14804 KB Output is correct
4 Correct 27 ms 14804 KB Output is correct
5 Correct 28 ms 14812 KB Output is correct
6 Correct 27 ms 14700 KB Output is correct
7 Correct 36 ms 14804 KB Output is correct
8 Correct 27 ms 14804 KB Output is correct
9 Correct 25 ms 14808 KB Output is correct
10 Correct 163 ms 22896 KB Output is correct
11 Correct 114 ms 27452 KB Output is correct
12 Correct 370 ms 34752 KB Output is correct
13 Correct 153 ms 28008 KB Output is correct
14 Correct 200 ms 29868 KB Output is correct
15 Correct 27 ms 15008 KB Output is correct
16 Correct 26 ms 14924 KB Output is correct
17 Correct 29 ms 14940 KB Output is correct
18 Correct 116 ms 34104 KB Output is correct
19 Correct 111 ms 33988 KB Output is correct
20 Correct 124 ms 34096 KB Output is correct
21 Correct 287 ms 30804 KB Output is correct
22 Correct 224 ms 32932 KB Output is correct
23 Correct 141 ms 30088 KB Output is correct
24 Correct 136 ms 27724 KB Output is correct
25 Correct 108 ms 36136 KB Output is correct
26 Correct 291 ms 32164 KB Output is correct
27 Correct 246 ms 32276 KB Output is correct
28 Correct 128 ms 29372 KB Output is correct
29 Correct 120 ms 27096 KB Output is correct
30 Correct 110 ms 35548 KB Output is correct
31 Correct 33 ms 15588 KB Output is correct
32 Correct 57 ms 19300 KB Output is correct
33 Correct 56 ms 19296 KB Output is correct
34 Correct 60 ms 19364 KB Output is correct
35 Correct 39 ms 17108 KB Output is correct
36 Correct 51 ms 21076 KB Output is correct
37 Correct 55 ms 25120 KB Output is correct
38 Correct 77 ms 18036 KB Output is correct
39 Correct 205 ms 26380 KB Output is correct
40 Correct 262 ms 26648 KB Output is correct
41 Correct 431 ms 32548 KB Output is correct
42 Correct 139 ms 27324 KB Output is correct
43 Correct 220 ms 29088 KB Output is correct
44 Correct 166 ms 29708 KB Output is correct
45 Correct 91 ms 18192 KB Output is correct
46 Correct 248 ms 26856 KB Output is correct
47 Correct 263 ms 26744 KB Output is correct
48 Correct 431 ms 33292 KB Output is correct
49 Correct 142 ms 28072 KB Output is correct
50 Correct 235 ms 29904 KB Output is correct
51 Correct 175 ms 30420 KB Output is correct