oj.uz

Submission #648829

# Submission time Handle Problem Language Result Execution time Memory
648829 2022-10-08T12:34:17 Z ymm Regions (IOI09_regions) C++17
100 / 100
 4383 ms 30116 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
 
const int S = 512;
const int N = 200'010 + S;
const int R = 25'010 + S;
int reg[N];
vector<int> reg_st_list[R];
vector<int> reg_list[R];
int cnt_reg[R];
int comp_big[R];
vector<int> big_list;
int ans_big[N/S][R];
int cnt_anc[R];
vector<int> A[N];
int st[N], ft[N];
int n, r, q;

void dfs(int v, int &t)
{
	st[v] = t++;
	reg_st_list[reg[v]].push_back(st[v]);
	for (int big : big_list)
		ans_big[comp_big[big]][reg[v]] += cnt_anc[big];
	cnt_anc[reg[v]]++;
	for (int u : A[v])
		dfs(u, t);
	cnt_anc[reg[v]]--;
	ft[v] = t;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> r >> q;
	cin >> reg[0];
	--reg[0];
	Loop (i,1,n) {
		int p;
		cin >> p >> reg[i];
		--reg[i];
		A[p-1].push_back(i);
	}
	Loop (i,0,n) {
		reg_list[reg[i]].push_back(i);
		cnt_reg[reg[i]]++;
	}
	Loop (i,0,r) {
		if (cnt_reg[i] >= S) {
			comp_big[i] = big_list.size();
			big_list.push_back(i);
		}
	}
	dfs(0, *new int(0));
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		--r1; --r2;
		if (cnt_reg[r1] >= S) {
			cout << ans_big[comp_big[r1]][r2] << '\n';
		} else {
			int ans = 0;
			for (int v : reg_list[r1]) {
				auto it1 = lower_bound(reg_st_list[r2].begin(), reg_st_list[r2].end(), st[v]);
				auto it2 = lower_bound(reg_st_list[r2].begin(), reg_st_list[r2].end(), ft[v]);
				ans += it2 - it1;
			}
			cout << ans << '\n';
		}
		cout.flush();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6224 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 5 ms 6224 KB Output is correct
4 Correct 7 ms 6224 KB Output is correct
5 Correct 14 ms 6224 KB Output is correct
6 Correct 20 ms 6352 KB Output is correct
7 Correct 37 ms 6224 KB Output is correct
8 Correct 31 ms 6352 KB Output is correct
9 Correct 57 ms 6736 KB Output is correct
10 Correct 79 ms 6736 KB Output is correct
11 Correct 121 ms 7112 KB Output is correct
12 Correct 156 ms 7632 KB Output is correct
13 Correct 195 ms 7168 KB Output is correct
14 Correct 207 ms 7888 KB Output is correct
15 Correct 237 ms 11020 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1600 ms 11184 KB Output is correct
2 Correct 1917 ms 9816 KB Output is correct
3 Correct 2897 ms 13288 KB Output is correct
4 Correct 299 ms 7888 KB Output is correct
5 Correct 285 ms 9960 KB Output is correct
6 Correct 1487 ms 9296 KB Output is correct
7 Correct 1554 ms 10260 KB Output is correct
8 Correct 1357 ms 16336 KB Output is correct
9 Correct 2434 ms 16088 KB Output is correct
10 Correct 4383 ms 22096 KB Output is correct
11 Correct 4206 ms 15804 KB Output is correct
12 Correct 1461 ms 17212 KB Output is correct
13 Correct 2137 ms 17652 KB Output is correct
14 Correct 2389 ms 19104 KB Output is correct
15 Correct 3316 ms 22836 KB Output is correct
16 Correct 3182 ms 29884 KB Output is correct
17 Correct 2714 ms 30116 KB Output is correct