Submission #998179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998179	2024-06-13T11:32:29 Z	BF001	Regions (IOI09_regions)	C++17	0 / 100	173 ms	34128 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);

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

	while (q--){
		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:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   if (rg[i].size() < blsiz) continue;
      |       ~~~~~~~~~~~~~^~~~~~~

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	2 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	3 ms	9048 KB	Time limit exceeded (wall clock)
10	Execution timed out	4 ms	9048 KB	Time limit exceeded (wall clock)
11	Execution timed out	6 ms	9304 KB	Time limit exceeded (wall clock)
12	Execution timed out	5 ms	9816 KB	Time limit exceeded (wall clock)
13	Execution timed out	6 ms	9560 KB	Time limit exceeded (wall clock)
14	Execution timed out	9 ms	10072 KB	Time limit exceeded (wall clock)
15	Execution timed out	9 ms	13656 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	40 ms	13140 KB	Time limit exceeded (wall clock)
2	Execution timed out	31 ms	11608 KB	Time limit exceeded (wall clock)
3	Execution timed out	23 ms	15448 KB	Time limit exceeded (wall clock)
4	Execution timed out	7 ms	10072 KB	Time limit exceeded (wall clock)
5	Execution timed out	8 ms	11608 KB	Time limit exceeded (wall clock)
6	Execution timed out	73 ms	12908 KB	Time limit exceeded (wall clock)
7	Execution timed out	89 ms	14160 KB	Time limit exceeded (wall clock)
8	Execution timed out	106 ms	22868 KB	Time limit exceeded (wall clock)
9	Execution timed out	42 ms	16832 KB	Time limit exceeded (wall clock)
10	Execution timed out	173 ms	34128 KB	Time limit exceeded (wall clock)
11	Execution timed out	37 ms	16216 KB	Time limit exceeded (wall clock)
12	Execution timed out	55 ms	18000 KB	Time limit exceeded (wall clock)
13	Execution timed out	62 ms	18512 KB	Time limit exceeded (wall clock)
14	Execution timed out	167 ms	19536 KB	Time limit exceeded (wall clock)
15	Execution timed out	44 ms	24516 KB	Time limit exceeded (wall clock)
16	Execution timed out	48 ms	33360 KB	Time limit exceeded (wall clock)
17	Execution timed out	85 ms	32980 KB	Time limit exceeded (wall clock)