oj.uz

답안 #424214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424214 2021-06-11T18:08:33 Z valerikk Arboras (RMI20_arboras) C++17
24 / 100
 809 ms 18076 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], tin[N], tout[N], T = 0;
int sum = 0;
int fen[N];

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

int top(int v) {
    while (v != 0 && v == best[p[v]]) v = p[v];
    return v;
}

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] = T++;
    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] = T;
}

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]);
    cout << sum << "\n";
    cin >> q;
    //int query_id = 0;
    while (q--) {
        int v, add;
        cin >> v >> add;
        int kek = v;
        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]];
                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;
}

Compilation message

arboras.cpp: In function 'int main()':
arboras.cpp:115:13: warning: unused variable 'kek' [-Wunused-variable]
  115 |         int kek = v;
      |             ^~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2892 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 16112 KB Output is correct
2 Correct 74 ms 14784 KB Output is correct
3 Correct 91 ms 15240 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 809 ms 18076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2892 KB Output is correct
2 Correct 4 ms 2892 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct
4 Correct 167 ms 16112 KB Output is correct
5 Correct 74 ms 14784 KB Output is correct
6 Correct 91 ms 15240 KB Output is correct
7 Incorrect 809 ms 18076 KB Output isn't correct
8 Halted 0 ms 0 KB -