Submission #1351309

#TimeUsernameProblemLanguageResultExecution timeMemory
1351309hminhatMigration Plan (JOI25_migration)C++20
0 / 100
7633 ms1565276 KiB
/*	
	ROAD TO TST 
*/
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define el "\n"
#define pb push_back
#define all(v) v.begin(), v.end()

#define rep(i, x, y) for(int i = x, _y = y; i <= _y; i++)
#define rev(i, x, y) for(int i = x, _y = y; i >= _y; i--)

void file() {
	#define name "test"
	if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	else {
		#undef name
		#define name "C:\\Users\\hminh\\Desktop\\2026\\AIO\\test"
		if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	}
}

const int nmax = 2e6 + 7;

int n, p[nmax], k[nmax], q, h[nmax], st[nmax], en[nmax], timedfs = 0;
vector<int> g[nmax];

void dfs(int u) {
	st[u] = ++timedfs;
	for(int v : g[u]) {
		h[v] = h[u] + 1;
		dfs(v);
	}
	en[u] = timedfs;
}

struct segtree {
	struct node {
		int sum, l, r, cnt;
		node(int _sum = 0, int _l = 0, int _r = 0, int _cnt = 0) {
			sum = _sum, l = _l, r = _r, cnt = _cnt;
		}
	} it[20 * nmax];
	int root[nmax], cur;

	int new_node() {
		++cur;
		it[cur] = node();
		return cur;
	}

	void update(int& id, int l, int r, int u, int val) {
		if(!id) id = new_node();
		if(l == r) {
			it[id].sum += val;
			it[id].cnt = 1;
			return;
		}
		int mid = (l + r) >> 1;
		if(u <= mid) update(it[id].l, l, mid, u, val);
		else update(it[id].r, mid + 1, r, u, val);
		it[id].sum = it[it[id].l].sum + it[it[id].r].sum;
		it[id].cnt = it[it[id].l].cnt + it[it[id].r].cnt;
	}

	int get(int id, int l, int r, int u, int v) {
		if(l > v || u > r || !id) return 0;
		if(l >= u && v >= r) return it[id].sum;
		int mid = (l + r) >> 1;
		return get(it[id].l, l, mid, u, v) + get(it[id].r, mid + 1, r, u, v);
	}

	int merge(int a, int b) {
		if(!a) return b;
		if(!b) return a;
		if(it[a].cnt < it[b].cnt) swap(a, b);
		it[a].l = merge(it[a].l, it[b].l);
		it[a].r = merge(it[a].r, it[b].r);
		it[a].sum = it[it[a].l].sum + it[it[a].r].sum;
		it[a].cnt = 1 + it[it[a].l].cnt + it[it[a].r].cnt;
		return a;
	}

} tr;

int main()
{
	file();
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	rep(i, 2, n) {
		cin >> p[i];
		g[p[i]].pb(i);
	}
	rep(i, 1, n) cin >> k[i];
	dfs(1);
	rep(i, 1, n) {
		tr.update(tr.root[h[i]], 1, n, st[i], k[i]);
	}
	cin >> q;
	while(q -- ) {
		int t;
		cin >> t;
		if(t == 1) {
			int x, y;
			cin >> x >> y;
			tr.root[y] = tr.merge(tr.root[y], tr.root[x]);
			tr.root[x] = 0;
		}
		else if(t == 2) {
			int u, v;
			cin >> u >> v;
			tr.update(tr.root[h[u]], 1, n, st[u], v);
		}
		else {
			int u;
			cin >> u;
			cout << tr.get(tr.root[h[u]], 1, n, st[u], en[u]) << el;
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void file()':
Main.cpp:21:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...