Submission #998205

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998205	2024-06-13T11:53:29 Z	BF001	Regions (IOI09_regions)	C++17	0 / 100	186 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, ii, r1, r2;
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 (ii = 1; ii <= q; ii++){
		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	2 ms	8792 KB	Time limit exceeded (wall clock)
2	Execution timed out	2 ms	8788 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	8788 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	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	4 ms	9816 KB	Time limit exceeded (wall clock)
13	Execution timed out	5 ms	9560 KB	Time limit exceeded (wall clock)
14	Execution timed out	12 ms	10072 KB	Time limit exceeded (wall clock)
15	Execution timed out	8 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	24 ms	15448 KB	Time limit exceeded (wall clock)
4	Execution timed out	9 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	75 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	109 ms	22860 KB	Time limit exceeded (wall clock)
9	Execution timed out	30 ms	16720 KB	Time limit exceeded (wall clock)
10	Execution timed out	186 ms	34128 KB	Time limit exceeded (wall clock)
11	Execution timed out	38 ms	16208 KB	Time limit exceeded (wall clock)
12	Execution timed out	75 ms	18000 KB	Time limit exceeded (wall clock)
13	Execution timed out	56 ms	18512 KB	Time limit exceeded (wall clock)
14	Execution timed out	165 ms	19536 KB	Time limit exceeded (wall clock)
15	Execution timed out	45 ms	24400 KB	Time limit exceeded (wall clock)
16	Execution timed out	50 ms	33360 KB	Time limit exceeded (wall clock)
17	Execution timed out	82 ms	33020 KB	Time limit exceeded (wall clock)