제출 #1341889

#제출 시각아이디문제언어결과실행 시간메모리
1341889SpyrosAlivMigration Plan (JOI25_migration)C++20
8 / 100
591 ms115956 KiB
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+5;
const int MD = 25;

vector<vector<int>> act(MN), tree(MN);
bool isAct[MN];
int cnt[MN], dep[MN], par[MN], anc[MN][MD];
int n, q;

void get_depths(int node) {
    act[dep[node]].push_back(node);
    isAct[node] = true;
    for (auto next: tree[node]) {
        dep[next] = dep[node] + 1;
        get_depths(next);
    }
}

void add(int u, int x) {
    cnt[u] += x;
    if (isAct[u] == false) {
        isAct[u] = true;
        act[dep[u]].push_back(u);
    }
}

void solve() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> par[i];
        tree[par[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        add(i, x);
    }
    get_depths(1);
    for (int i = 1; i <= n; i++) {
        anc[i][0] = par[i];
        for (int j = 1; j < MD; j++) {
            anc[i][j] = par[anc[i][j-1]];
        }
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y;
            int totUp = x - y - 1;
            for (auto xx: act[x]) {
                add(anc[xx][totUp], cnt[xx]);
                cnt[xx] = 0;
                isAct[xx] = false;
            }
            act[x].clear();
        }
        else if (t == 2) {
            int u, x; cin >> u >> x;
            add(u, x);
        }
        else if (t == 3) {
            int u; cin >> u;
            cout << cnt[u] << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...