Submission #998198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998198	2024-06-13T11:49:04 Z	BF001	Regions (IOI09_regions)	C++17	0 / 100	194 ms	34076 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);
	}

	for (int i = 1; i <= q; i++){
		int r1, r2;
		cin >> r1 >> r2;
		// if (rg[r1].size() >= blsiz){
		// 	cout << gt[idx[r1]][r2] << " 1\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	1 ms	8792 KB	Time limit exceeded (wall clock)
3	Execution timed out	1 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	2 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	3 ms	9048 KB	Time limit exceeded (wall clock)
11	Execution timed out	4 ms	9304 KB	Time limit exceeded (wall clock)
12	Execution timed out	6 ms	9816 KB	Time limit exceeded (wall clock)
13	Execution timed out	7 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	12 ms	13656 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	39 ms	13144 KB	Time limit exceeded (wall clock)
2	Execution timed out	32 ms	11608 KB	Time limit exceeded (wall clock)
3	Execution timed out	32 ms	15440 KB	Time limit exceeded (wall clock)
4	Execution timed out	7 ms	10324 KB	Time limit exceeded (wall clock)
5	Execution timed out	8 ms	11608 KB	Time limit exceeded (wall clock)
6	Execution timed out	77 ms	12880 KB	Time limit exceeded (wall clock)
7	Execution timed out	89 ms	14160 KB	Time limit exceeded (wall clock)
8	Execution timed out	97 ms	22864 KB	Time limit exceeded (wall clock)
9	Execution timed out	32 ms	16724 KB	Time limit exceeded (wall clock)
10	Execution timed out	194 ms	34076 KB	Time limit exceeded (wall clock)
11	Execution timed out	42 ms	16256 KB	Time limit exceeded (wall clock)
12	Execution timed out	58 ms	18000 KB	Time limit exceeded (wall clock)
13	Execution timed out	47 ms	18512 KB	Time limit exceeded (wall clock)
14	Execution timed out	163 ms	19540 KB	Time limit exceeded (wall clock)
15	Execution timed out	64 ms	24400 KB	Time limit exceeded (wall clock)
16	Execution timed out	46 ms	33360 KB	Time limit exceeded (wall clock)
17	Execution timed out	80 ms	33104 KB	Time limit exceeded (wall clock)