제출 #1064991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064991		belgianbot	Regions (IOI09_regions)	C++17	50 / 100	8064 ms	131072 KiB

regions

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt = 0, N, SQRT, R;

struct segTree {
	vector<map<int,int>> t;
	void build() {
		for (int i = N - 1; i > 0; i--) {
			for (auto x : t[i << 1]) t[i][x.first] += x.second;
			for (auto x : t[i << 1 | 1]) t[i][x.first] += x.second;
		}
	}
	ll query(int l, int r, int c) {
		ll res = 0;
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l&1){
				if (t[l].count(c)) res += t[l][c];
				l++;
			}
			if (r&1) {
				r--;
				if (t[r].count(c)) res += t[r][c];
			}
		}
		return res;
	}
};
segTree seg;
vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, vector<ll>> col;


map<int,int> dfs(int x) {
	seg.t[cnt + N][a[x]] = 1;
	in[x] = cnt++;
	
	map<int,int> curr;
	for (int y : child[x]) {
		map<int,int> mp = dfs(y);
		if (mp.size() > curr.size()) swap(mp, curr);
		for (auto z : mp) curr[z.first] += z.second;
	}
	if (occ[a[x]] > SQRT) for (auto z : curr) col[a[x]][z.first] += z.second;
	curr[a[x]]++;
	out[x] = cnt;
	return curr;
	
}

signed main() {
	ios::sync_with_stdio(false);
	int Q; cin >> N >> R >> Q;
	a.resize(N); child.resize(N); in.resize(N); out.resize(N); cin >> a[0]; a[0]--;
	occ.resize(R, 0); occ[a[0]]++;
	seg.t.resize(2 * N);
	for (int i = 1; i < N; i++) {
		int b; cin >> b >> a[i]; b--; a[i]--; occ[a[i]]++;
		child[b].push_back(i);
	}
	SQRT=sqrt(N);
	vector<vector<int>> temp(R);
	for (int i = 0; i < N; i++) {
		if (occ[a[i]] <= SQRT) temp[a[i]].push_back(i);

	}
	for (int i = 0; i < R; i++) {
		if (occ[i] > SQRT) col[i].resize(R);
	}
	dfs(0);
	seg.build();
	
	
	while (Q--) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (occ[r1] > SQRT) cout << col[r1][r2] << '\n';
		
		else {
			ll ans = 0;
			for (int x : temp[r1]) {
				ans += seg.query(in[x] + 1, out[x], r2);
			}
			cout << ans << '\n';
		}
	}
		
	return 0;
}
		
	
	
	

• Subtask 1: 15 / 15
• Subtask 2: 35 / 85