oj.uz

Submission #424280

# Submission time Handle Problem Language Result Execution time Memory
424280 2021-06-11T18:56:24 Z valerikk Arboras (RMI20_arboras) C++17
100 / 100
 153 ms 23384 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 1e5 + 7;
const int md = 1e9 + 7;

int n, q;
int p[N], d[N];
vector<int> g[N];
int best[N], best2[N];
int dp[N], dp2[N];
int hld[N];
int sz[N];
int tin[N], tout[N];
int sum = 0;
int fen[N];
vector<int> ord;
int ind[2 * N];

void upd(int pos, int val) {
    int v = pos + n;
    ind[v] = val == 0 ? pos : -1;
    while (v > 1) {
        ind[v >> 1] = max(ind[v], ind[v ^ 1]);
        v >>= 1;
    }
}

int get_ind(int l, int r) {
    int vl = l + n, vr = r + n;
    int ret = -1;
    while (vl < vr) {
        if (vl & 1) ret = max(ret, ind[vl++]);
        if (vr & 1) ret = max(ret, ind[--vr]);
        vl >>= 1, vr >>= 1;
    }
    return ret;
}

void build() {
    for (int i = 0; i < n; ++i) ind[i + n] = i;
    for (int i = n - 1; i > 0; --i) ind[i] = max(ind[i << 1], ind[i << 1 | 1]);
}

bool is_par(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int top(int v) {
    while (v != -1) {
        int i = get_ind(tin[hld[v]], tin[v] + 1);
        if (i != -1) return ord[i];
        v = p[hld[v]];
    }
    assert(0);
    return -1;
}

void add_fen(int pos, int val) {
    for (int i = pos + 1; i < N; i += i & -i) fen[i] += val;
}

void add_fen(int l, int r, int val) {
    sum += (r - l) * val;
    add_fen(l, val);
    add_fen(r, -val);
}

int get_fen(int r) {
    int res = 0;
    for (; r > 0; r -= r & -r) res += fen[r];
    return res;
}

void add_path(int v, int u, int val) {
    while (u != -1 && is_par(v, u)) {
        if (is_par(v, hld[u])) {
            add_fen(tin[hld[u]], tin[u] + 1, val);
        } else {
            add_fen(tin[v], tin[u] + 1, val);
        }
        u = p[hld[u]];
    }
}

int get_dp(int v) {
    return get_fen(tin[v] + 1);
}

void dfs(int v) {
    best[v] = best2[v] = -1;
    dp[v] = dp2[v] = 0;
    sz[v] = 1;
    for (int u : g[v]) {
        dfs(u);
        sz[v] += sz[u];
        if (dp[u] + d[u] > dp[v]) {
            dp2[v] = dp[v], best2[v] = best[v];
            dp[v] = dp[u] + d[u], best[v] = u;
        } else if (dp[u] + d[u] > dp2[v]) {
            dp2[v] = dp[u] + d[u];
            best2[v] = u;
        }
    }
    if (best[v] == -1 && !g[v].empty()) best[v] = g[v][0];
    if (best2[v] == -1 && g[v].size() >= 2) best2[v] = g[v][1];
    sum += dp2[v];
}

void dfs1(int v) {
    tin[v] = ord.size();
    ord.push_back(v);
    for (int &u : g[v]) {
        if (sz[u] > sz[g[v][0]]) swap(g[v][0], u);
    }
    for (int u : g[v]) {
        hld[u] = u == g[v][0] ? hld[v] : u;
        dfs1(u);
    }
    tout[v] = ord.size();
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    p[0] = -1;
    for (int i = 1; i < n; ++i) {
        cin >> p[i];
        g[p[i]].push_back(i);
    }
    for (int i = 1; i < n; ++i) {
        cin >> d[i];
    }
    dfs(0);
    dfs1(0);
    for (int i = 0; i < n; ++i) add_path(i, i, dp[i]);
    build();
    for (int i = 1; i < n; ++i) {
        if (i == best[p[i]]) upd(tin[i], 1);
    }
    cout << sum % md << "\n";
    cin >> q;
    //int query_id = 0;
    while (q--) {
        int v, add;
        cin >> v >> add;
        d[v] += add;
        if (v == best[p[v]]) {
            add_path(top(v), p[v], add);
            /*cout << "query_id: " << query_id << endl;
            cout << "top: " << top(v) << endl;
            cout << "bottom: " << p[v] << endl;
            cout << "sum: " << sum << endl;*/
            v = top(v);
        }
        while (v != 0) {
            if (get_dp(v) + d[v] > get_dp(p[v])) {
                sum += get_dp(p[v]) - dp2[p[v]];
                dp2[p[v]] = get_dp(p[v]), best2[p[v]] = best[p[v]];
                upd(tin[best[p[v]]], 0);
                upd(tin[v], 1);
                best[p[v]] = v;
                add_path(top(p[v]), p[v], get_dp(v) + d[v] - get_dp(p[v]));
            } else {
                if (get_dp(v) + d[v] > dp2[p[v]]) {
                    sum += get_dp(v) + d[v] - dp2[p[v]];
                    dp2[p[v]] = get_dp(v) + d[v], best2[p[v]] = v;
                }
                break;
            }
            v = top(p[v]);
        }
        /*cout << "top: ";
        for (int i = 0; i < n; ++i) cout << top(i) << " ";
        cout << endl;
        cout << "best: ";
        for (int i = 0; i < n; ++i) cout << best[i] << " ";
        cout << endl;*/
        cout << sum % md << "\n";
        //++query_id;
    }
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 16544 KB Output is correct
2 Correct 69 ms 15348 KB Output is correct
3 Correct 77 ms 15868 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 18272 KB Output is correct
2 Correct 96 ms 20536 KB Output is correct
3 Correct 94 ms 19064 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2892 KB Output is correct
2 Correct 3 ms 2892 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 153 ms 16544 KB Output is correct
5 Correct 69 ms 15348 KB Output is correct
6 Correct 77 ms 15868 KB Output is correct
7 Correct 113 ms 18272 KB Output is correct
8 Correct 96 ms 20536 KB Output is correct
9 Correct 94 ms 19064 KB Output is correct
10 Correct 126 ms 20280 KB Output is correct
11 Correct 97 ms 22680 KB Output is correct
12 Correct 98 ms 18868 KB Output is correct
13 Correct 86 ms 22544 KB Output is correct
14 Correct 85 ms 23384 KB Output is correct