Submission #1082422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082422	2024-08-31T10:15:01 Z	Thunnus	Regions (IOI09_regions)	C++17	100 / 100	2632 ms	47748 KB

regions

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size() 

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, r, q;
	cin >> n >> r >> q;
	const int SZ = ceil(sqrt(n));
	vi par(n), reg(n);
	vvi children(n), precalc(r), reg_tins(r), r2v(r);
	cin >> reg[0];
	reg[0]--;
	for(int i = 1; i < n; i++){
		cin >> par[i] >> reg[i];
		par[i]--, reg[i]--;
		children[par[i]].emplace_back(i);
	}

	vi tin(n), tout(n);
	int timer = 0;
	function<void(int)> euler = [&](int v) -> void {
		tin[v] = timer++;
		reg_tins[reg[v]].emplace_back(tin[v]);
		r2v[reg[v]].emplace_back(v);
		for(int &u : children[v]){
			euler(u);
		}
		tout[v] = timer - 1;
	};
	euler(0);

	int curreg = -1, curcnt = 0;
	function<void(int)> dfs = [&](int v) -> void {
		if(curreg == reg[v]){
			curcnt++;
		}
		else{
			precalc[curreg][reg[v]] += curcnt;
		}
		for(int &u : children[v]){
			dfs(u);
		}
		curcnt -= (curreg == reg[v]);
	};

	for(int i = 0; i < r; i++){
		if(sz(r2v[i]) >= SZ){
			curreg = i, curcnt = 0;
			precalc[i].resize(r);
			dfs(0);
		}
	}

	while(q--){
		int r1, r2;
		cin >> r1 >> r2;
		r1--, r2--;
		if(sz(r2v[r1]) >= SZ){
			cout << precalc[r1][r2] << endl;
		}
		else{
			int ans = 0;
			for(int &v : r2v[r1]){
				ans += upper_bound(reg_tins[r2].begin(), reg_tins[r2].end(), tout[v]) - lower_bound(reg_tins[r2].begin(), reg_tins[r2].end(), tin[v]);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	2 ms	344 KB	Output is correct
5	Correct	5 ms	344 KB	Output is correct
6	Correct	13 ms	600 KB	Output is correct
7	Correct	14 ms	600 KB	Output is correct
8	Correct	18 ms	764 KB	Output is correct
9	Correct	29 ms	1368 KB	Output is correct
10	Correct	44 ms	1368 KB	Output is correct
11	Correct	69 ms	2136 KB	Output is correct
12	Correct	95 ms	3072 KB	Output is correct
13	Correct	109 ms	2932 KB	Output is correct
14	Correct	169 ms	3852 KB	Output is correct
15	Correct	179 ms	8140 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1460 ms	9640 KB	Output is correct
2	Correct	1637 ms	8536 KB	Output is correct
3	Correct	2281 ms	12888 KB	Output is correct
4	Correct	190 ms	4144 KB	Output is correct
5	Correct	282 ms	6844 KB	Output is correct
6	Correct	458 ms	10136 KB	Output is correct
7	Correct	941 ms	13132 KB	Output is correct
8	Correct	893 ms	25244 KB	Output is correct
9	Correct	1663 ms	19908 KB	Output is correct
10	Correct	2400 ms	47748 KB	Output is correct
11	Correct	2632 ms	22624 KB	Output is correct
12	Correct	957 ms	22632 KB	Output is correct
13	Correct	1370 ms	23400 KB	Output is correct
14	Correct	1771 ms	26956 KB	Output is correct
15	Correct	2467 ms	30044 KB	Output is correct
16	Correct	2495 ms	38768 KB	Output is correct
17	Correct	2387 ms	40472 KB	Output is correct