Submission #998272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998272	2024-06-13T13:09:30 Z	BF001	Regions (IOI09_regions)	C++17	0 / 100	206 ms	77036 KB

regions

#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define M 25005 

int n, r, q, h[N], tin[N], tout[N], tim, idx[N], cnt = -1, blsiz;
vector<int> adj[N], rg[M], v[M];
vector<vector<int>> gt;

void init(int u){
	tin[u] = ++tim;
	rg[h[u]].push_back(tin[u]);
	v[h[u]].push_back(u);
	for (auto x : adj[u]){
		init(x);
	}
	tout[u] = tim;
}

void dfs(int u, int typ, int cnt){
	int ncnt = cnt;
	if (h[u] == typ) ncnt++;
	for (auto x : adj[u]){
		gt[idx[typ]][h[x]] += ncnt;
		dfs(x, typ, ncnt);
	} 	
}

int find(int typ, int val){
	int l = 0, r = rg[typ].size() - 1, rt = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (rg[typ][mid] <= val){
			rt = mid + 1;
			l = mid + 1;
		}
		else r = mid - 1; 
	}
	return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
	cin >> n >> r >> q;
	cin >> h[1];
	for (int i = 2; i <= n; i++){
		int p;
		cin >> p >> h[i];
		adj[p].push_back(i);
	}   

	blsiz = sqrt(n);

	gt.resize(blsiz + 1);
	for(int i = 0; i <= blsiz; i++) gt[i].resize(r + 1);

	init(1);
	for (int i = 1; i <= r; i++){
		if (rg[i].size() < blsiz) continue;
		idx[i] = ++cnt;
		dfs(1, i, 0);
	}

	for (int i = 1; i <= q; i++){
		int r1, r2;
		cin >> r1 >> r2;
		if (rg[r1].size() >= blsiz){
			cout << gt[idx[r1]][r2] << "\n";
			
			continue;
		}
		int res = 0;
		for (auto x : v[r1]){
			res += find(r2, tout[x]) - find(r2, tin[x] - 1);
			break;
		}
		cout << res << "\n";
	}

    return 0;
}     

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:62:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   if (rg[i].size() < blsiz) continue;
      |       ~~~~~~~~~~~~~^~~~~~~
regions.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   if (rg[r1].size() >= blsiz){
      |       ~~~~~~~~~~~~~~^~~~~~~~

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1 ms	8792 KB	Time limit exceeded (wall clock)
2	Execution timed out	2 ms	8792 KB	Time limit exceeded (wall clock)
3	Execution timed out	2 ms	8792 KB	Time limit exceeded (wall clock)
4	Execution timed out	1 ms	8792 KB	Time limit exceeded (wall clock)
5	Execution timed out	1 ms	8792 KB	Time limit exceeded (wall clock)
6	Execution timed out	2 ms	8792 KB	Time limit exceeded (wall clock)
7	Execution timed out	2 ms	8792 KB	Time limit exceeded (wall clock)
8	Execution timed out	2 ms	8792 KB	Time limit exceeded (wall clock)
9	Execution timed out	2 ms	9304 KB	Time limit exceeded (wall clock)
10	Execution timed out	3 ms	9304 KB	Time limit exceeded (wall clock)
11	Execution timed out	4 ms	9560 KB	Time limit exceeded (wall clock)
12	Execution timed out	4 ms	10072 KB	Time limit exceeded (wall clock)
13	Execution timed out	6 ms	9560 KB	Time limit exceeded (wall clock)
14	Execution timed out	10 ms	10072 KB	Time limit exceeded (wall clock)
15	Execution timed out	10 ms	13912 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	39 ms	13400 KB	Time limit exceeded (wall clock)
2	Execution timed out	32 ms	11864 KB	Time limit exceeded (wall clock)
3	Execution timed out	23 ms	15704 KB	Time limit exceeded (wall clock)
4	Execution timed out	8 ms	12888 KB	Time limit exceeded (wall clock)
5	Execution timed out	9 ms	15448 KB	Time limit exceeded (wall clock)
6	Execution timed out	77 ms	17496 KB	Time limit exceeded (wall clock)
7	Execution timed out	98 ms	22608 KB	Time limit exceeded (wall clock)
8	Execution timed out	111 ms	31212 KB	Time limit exceeded (wall clock)
9	Execution timed out	58 ms	39504 KB	Time limit exceeded (wall clock)
10	Execution timed out	206 ms	64852 KB	Time limit exceeded (wall clock)
11	Execution timed out	62 ms	60100 KB	Time limit exceeded (wall clock)
12	Execution timed out	67 ms	45136 KB	Time limit exceeded (wall clock)
13	Execution timed out	82 ms	45908 KB	Time limit exceeded (wall clock)
14	Execution timed out	188 ms	53076 KB	Time limit exceeded (wall clock)
15	Execution timed out	63 ms	67976 KB	Time limit exceeded (wall clock)
16	Execution timed out	67 ms	77036 KB	Time limit exceeded (wall clock)
17	Execution timed out	102 ms	66384 KB	Time limit exceeded (wall clock)