Submission #1364164

#TimeUsernameProblemLanguageResultExecution timeMemory
1364164vlomaczkMigration Plan (JOI25_migration)C++20
25 / 100
7609 ms814524 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll M = 2'000'010;
vector<vector<ll>> g(M);
vector<ll> depth(M);
vector<vector<ll>> D(M);
ll maxlog = 20;
vector<vector<ll>> jump(M, vector<ll>(maxlog+1));

void dfs(ll v, ll p) {
	jump[v][0] = p;
	for(ll i=1; i<=maxlog; ++i) jump[v][i] = jump[jump[v][i-1]][i-1];
	D[depth[v]].push_back(v);
	for(auto u : g[v]) {
		depth[u] = depth[v] + 1;
		dfs(u,v);
	}
}

ll skok(ll v, ll x) {
	for(ll i=maxlog; i>=0; --i) {
		if(x >= (1<<i)) {
			x -= (1<<i);
			v=jump[v][i];
		}
	}
	return v;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n; cin >> n;
	vector<ll> p(n+1);
	for(ll i=2; i<=n; ++i) {
		cin >> p[i];
		g[p[i]].push_back(i);
	}
	vector<ll> A(n+1);
	for(ll i=1; i<=n; ++i) cin >> A[i];
	dfs(1,1);
	ll q; cin >> q;
	while(q--) {
		ll t; cin >> t;
		if(t==1) {
			ll a, b;
			cin >> a >> b;
			for(auto x : D[a]) {
				if(A[x]) {
					ll u = skok(x,a-b);
					if(A[u]==0) D[b].push_back(u);
					A[u] += A[x];
					A[x] = 0;
				}
			}
			while(D[a].size()) D[a].pop_back();
		} else if(t==2) {
			ll a,b;
			cin >> a >> b;
			A[a] += b;
			D[depth[a]].push_back(a);
		} else {
			ll x; cin >> x;
			cout << A[x] << "\n";
		}
	}	
	
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...