oj.uz

Submission #998171

# Submission time Handle Problem Language Result Execution time Memory
998171 2024-06-13T11:25:10 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 173 ms 34128 KB 
#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);
		// }
		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;
      |       ~~~~~~~~~~~~~^~~~~~~
regions.cpp:68:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   if (rg[r1].size() >= blsiz){
      |       ~~~~~~~~~~~~~~^~~~~~~~

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 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 1 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 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 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 13144 KB Time limit exceeded (wall clock)
2 Execution timed out 34 ms 11608 KB Time limit exceeded (wall clock)
3 Execution timed out 22 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 77 ms 12880 KB Time limit exceeded (wall clock)
7 Execution timed out 90 ms 14160 KB Time limit exceeded (wall clock)
8 Execution timed out 138 ms 22632 KB Time limit exceeded (wall clock)
9 Execution timed out 35 ms 16720 KB Time limit exceeded (wall clock)
10 Execution timed out 173 ms 34128 KB Time limit exceeded (wall clock)
11 Execution timed out 50 ms 16208 KB Time limit exceeded (wall clock)
12 Execution timed out 51 ms 18000 KB Time limit exceeded (wall clock)
13 Execution timed out 43 ms 18512 KB Time limit exceeded (wall clock)
14 Execution timed out 162 ms 19536 KB Time limit exceeded (wall clock)
15 Execution timed out 47 ms 24296 KB Time limit exceeded (wall clock)
16 Execution timed out 55 ms 33360 KB Time limit exceeded (wall clock)
17 Execution timed out 82 ms 33104 KB Time limit exceeded (wall clock)