oj.uz

Submission #749903

# Submission time Handle Problem Language Result Execution time Memory
749903 2023-05-28T23:10:28 Z doowey Arboras (RMI20_arboras) C++14
100 / 100
 187 ms 23004 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> 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 + 1;
const int MOD = (int)1e9 + 7;

vector<int> E[N];
int par[N];
ll w[N];
int n;
int sub[N];
int link[N];
int rig[N];
int tin[N];
int tout[N];
int nd[N];
int tt = -1;
ll dp0[N];
int big0[N];
ll dp1[N];

void dfs(int u){
    sub[u] = 1;
    dp0[u] = dp1[u] = 0ll;
    big0[u] = -1;
    for(auto x : E[u]){
        dfs(x);
        if(dp0[x] + w[x] > dp0[u]){
            big0[u] = x;
            dp1[u] = dp0[u];
            dp0[u] = dp0[x] + w[x];
        }
        else if(dp0[x] + w[x] > dp1[u]){
            dp1[u] = dp0[x] + w[x];
        }
        sub[u] += sub[x];
    }
}


void dfs1(int u){
    tt ++ ;
    tin[u] = tt;
    nd[tin[u]] = u;
    if(link[u] == -1) link[u] = u;
    rig[link[u]] = tin[u];
    int nx = -1;
    for(auto x : E[u]){
        if(nx == -1 || sub[x] > sub[nx]){
            nx = x;
        }
    }
    if(nx != -1){
        link[nx]=link[u];
    }
    if(nx != -1){
        dfs1(nx);
    }

    for(auto x : E[u]){
        if(x != nx)
            dfs1(x);
    }
    tout[u] = tt;
}

struct Node{
    ll dp;
    int id;
};

Node T[N * 4 + 24];

ll sum = 0;

void inc(ll y){
    y %= MOD;
    sum += y;
    if(sum < 0) sum += MOD;
    else if(sum >= MOD) sum -= MOD;
}

void build(int node, int cl, int cr){
    if(cl == cr){
        if(big0[nd[cl]] == -1 || link[big0[nd[cl]]] != link[nd[cl]])
            T[node].id = cl;
        else
            T[node].id = -1;
        T[node].dp = dp0[nd[cl]];
        inc(dp0[nd[cl]] + dp1[nd[cl]]);
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node].dp = 0ll;
    T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}

int query_id(int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr) return -1;
    if(cl >= tl && cr <= tr){
        return T[node].id;
    }
    int mid = (cl + cr) / 2;
    return max(query_id(node * 2, cl, mid, tl, tr), query_id(node * 2 + 1, mid + 1, cr, tl, tr));
}

void set_id(int node, int cl, int cr, int id, int p){
    if(cl == cr){
        T[node].id = p;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        set_id(node * 2, cl, mid, id, p);
    else
        set_id(node * 2 + 1, mid + 1, cr, id, p);
    T[node].id = max(T[node * 2].id, T[node * 2 + 1].id);
}

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

void add_dp(int node, int cl, int cr, int tl, int tr, ll W){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        inc((cr - cl + 1) * 1ll * W);
        T[node].dp += W;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    add_dp(node * 2, cl, mid, tl, tr, W);
    add_dp(node * 2 + 1, mid + 1, cr, tl, tr, W);
}

ll ask_dp(int node, int cl, int cr, int idx){
    push(node, cl, cr);
    if(cl == cr){
        return T[node].dp;
    }
    int mid = (cl + cr) / 2;
    if(mid >= idx)
        return ask_dp(node * 2, cl, mid, idx);
    else
        return ask_dp(node * 2 + 1, mid + 1, cr, idx);
}

ll get_dp(int node){
    return ask_dp(1, 0, n - 1, tin[node]);
}

ll add;

void check_up(int &v){
    ll f = get_dp(v) + w[v];
    ll par_dp = get_dp(par[v]);
    if(big0[par[v]] == v){
        add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
        v = par[v];
    }
    else{
        if(f > par_dp){
            add = f - par_dp;
            add_dp(1, 0, n - 1, tin[par[v]], tin[par[v]], add);
            if(link[par[v]] == link[v]){
                set_id(1, 0, n - 1, tin[par[v]], -1);
            }
            else{
                set_id(1, 0, n - 1, tin[par[v]], tin[par[v]]);
            }
            inc(par_dp-dp1[par[v]]);
            dp1[par[v]] = par_dp;
            big0[par[v]] = v;
            v=par[v];
        }
        else if(f > dp1[par[v]]){
            inc(f-dp1[par[v]]);
            dp1[par[v]] = f;
            v=0;
        }
        else{
            v = 0;
        }
    }
}

ll n0[N];
ll n1[N];

void dfs2(int u){
    n0[u] = n1[u] = 0ll;
    for(auto x : E[u]){
        dfs2(x);
        if(n0[x] + w[x] > n0[u]){
            n1[u] = n0[u];
            n0[u] = n0[x] + w[x];
        }
        else if(n0[x] + w[x] > n1[u]){
            n1[u] = n0[x] + w[x];
        }
    }
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    cin >> n;
    for(int i = 1; i < n; i ++ ){
        cin >> par[i];
        E[par[i]].push_back(i);
    }
    for(int i = 1; i < n; i ++ ){
        cin >> w[i];
    }
    for(int i = 0 ; i < n; i ++ ){
        link[i] = -1;

    }
    dfs(0);
    dfs1(0);
    build(1, 0, n - 1);


    dfs2(0);
    /*
    for(int i = 0; i < n; i ++ ){
        cout << "(" << get_dp(i) << "," << dp1[i] << ") ";
    }
    cout << "\n";
    for(int i = 0 ; i < n; i ++ ){
        cout << "[" << n0[i] << "," << n1[i] << "] ";
    }
    cout << "\n";
    */
    cout << sum << "\n";
    //return 0;
    int q;
    cin >> q;
    int v;
    int g;
    int i0, i1;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> v >> add;
        // implement ze walk up
        w[v] += add;
        //check_up(v);
        while(v > 0){
            if(v == link[v]){
                check_up(v);
            }
            else{
                g = query_id(1, 0, n - 1, tin[link[v]], tin[v] - 1);
                if(g == -1){
                    add_dp(1, 0, n - 1, tin[link[v]], tin[v] - 1, add);

                    v = link[v];

                }
                else{
                    add_dp(1, 0, n - 1, g + 1, tin[v] - 1, add);

                    v=nd[g + 1];
                    check_up(v);
                }
            }
        }
        //dfs2(0);
        /*
        for(int i = 0; i < n; i ++ ){
            cout << "(" << get_dp(i) << "," << dp1[i] << ") ";
        }
        cout << "\n";
        for(int i = 0 ; i < n; i ++ ){
            cout << "[" << n0[i] << "," << n1[i] << "] ";
        }
        cout << "\n";
        */
        cout << sum << "\n";
    }
    return 0;
}

Compilation message

arboras.cpp: In function 'int main()':
arboras.cpp:258:9: warning: unused variable 'i0' [-Wunused-variable]
  258 |     int i0, i1;
      |         ^~
arboras.cpp:258:13: warning: unused variable 'i1' [-Wunused-variable]
  258 |     int i0, i1;
      |             ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2844 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 16380 KB Output is correct
2 Correct 75 ms 15080 KB Output is correct
3 Correct 88 ms 15428 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 18188 KB Output is correct
2 Correct 95 ms 20692 KB Output is correct
3 Correct 92 ms 18548 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2844 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 187 ms 16380 KB Output is correct
5 Correct 75 ms 15080 KB Output is correct
6 Correct 88 ms 15428 KB Output is correct
7 Correct 122 ms 18188 KB Output is correct
8 Correct 95 ms 20692 KB Output is correct
9 Correct 92 ms 18548 KB Output is correct
10 Correct 131 ms 20356 KB Output is correct
11 Correct 89 ms 22496 KB Output is correct
12 Correct 98 ms 18356 KB Output is correct
13 Correct 103 ms 22204 KB Output is correct
14 Correct 95 ms 23004 KB Output is correct