oj.uz

Submission #998275

# Submission time Handle Problem Language Result Execution time Memory
998275 2024-06-13T13:21:12 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 209 ms 77016 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], cn = -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;
		cn += 1;
		idx[i] = cn;
		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:71:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   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 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 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 9304 KB Time limit exceeded (wall clock)
10 Execution timed out 4 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 5 ms 10072 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 9560 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 10072 KB Time limit exceeded (wall clock)
15 Execution timed out 9 ms 13912 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 45 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 22 ms 15704 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 12888 KB Time limit exceeded (wall clock)
5 Execution timed out 11 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 94 ms 22608 KB Time limit exceeded (wall clock)
8 Execution timed out 109 ms 31316 KB Time limit exceeded (wall clock)
9 Execution timed out 41 ms 39504 KB Time limit exceeded (wall clock)
10 Execution timed out 209 ms 64800 KB Time limit exceeded (wall clock)
11 Execution timed out 78 ms 60188 KB Time limit exceeded (wall clock)
12 Execution timed out 69 ms 45244 KB Time limit exceeded (wall clock)
13 Execution timed out 61 ms 45936 KB Time limit exceeded (wall clock)
14 Execution timed out 195 ms 53072 KB Time limit exceeded (wall clock)
15 Execution timed out 56 ms 67960 KB Time limit exceeded (wall clock)
16 Execution timed out 62 ms 77016 KB Time limit exceeded (wall clock)
17 Execution timed out 93 ms 66348 KB Time limit exceeded (wall clock)