oj.uz

Submission #998277

# Submission time Handle Problem Language Result Execution time Memory
998277 2024-06-13T13:27:25 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 193 ms 82256 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 = 500;
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);
	}   

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

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 8788 KB Time limit exceeded (wall clock)
4 Execution timed out 1 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 9304 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 9048 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 9304 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 10072 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 9816 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 10584 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 10072 KB Time limit exceeded (wall clock)
14 Execution timed out 6 ms 10328 KB Time limit exceeded (wall clock)
15 Execution timed out 8 ms 12888 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 28 ms 13376 KB Time limit exceeded (wall clock)
2 Execution timed out 39 ms 11860 KB Time limit exceeded (wall clock)
3 Execution timed out 23 ms 15960 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 18008 KB Time limit exceeded (wall clock)
5 Execution timed out 12 ms 21336 KB Time limit exceeded (wall clock)
6 Execution timed out 37 ms 24920 KB Time limit exceeded (wall clock)
7 Execution timed out 24 ms 31576 KB Time limit exceeded (wall clock)
8 Execution timed out 30 ms 38488 KB Time limit exceeded (wall clock)
9 Execution timed out 51 ms 46160 KB Time limit exceeded (wall clock)
10 Execution timed out 64 ms 70480 KB Time limit exceeded (wall clock)
11 Execution timed out 58 ms 65372 KB Time limit exceeded (wall clock)
12 Execution timed out 73 ms 49232 KB Time limit exceeded (wall clock)
13 Execution timed out 82 ms 49744 KB Time limit exceeded (wall clock)
14 Execution timed out 193 ms 57168 KB Time limit exceeded (wall clock)
15 Execution timed out 61 ms 73252 KB Time limit exceeded (wall clock)
16 Execution timed out 81 ms 82256 KB Time limit exceeded (wall clock)
17 Execution timed out 98 ms 70596 KB Time limit exceeded (wall clock)