oj.uz

Submission #998026

# Submission time Handle Problem Language Result Execution time Memory
998026 2024-06-13T08:25:06 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 184 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 1 ms 8792 KB Time limit exceeded (wall clock)
2 Execution timed out 2 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 1 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 2 ms 8792 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 8788 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 4 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 9760 KB Time limit exceeded (wall clock)
13 Execution timed out 7 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 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 12992 KB Time limit exceeded (wall clock)
2 Execution timed out 31 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 7 ms 10072 KB Time limit exceeded (wall clock)
5 Execution timed out 11 ms 11608 KB Time limit exceeded (wall clock)
6 Execution timed out 73 ms 12876 KB Time limit exceeded (wall clock)
7 Execution timed out 93 ms 14036 KB Time limit exceeded (wall clock)
8 Execution timed out 121 ms 22708 KB Time limit exceeded (wall clock)
9 Execution timed out 31 ms 16692 KB Time limit exceeded (wall clock)
10 Execution timed out 184 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 53 ms 17892 KB Time limit exceeded (wall clock)
13 Execution timed out 47 ms 18728 KB Time limit exceeded (wall clock)
14 Execution timed out 164 ms 19480 KB Time limit exceeded (wall clock)
15 Execution timed out 42 ms 24400 KB Time limit exceeded (wall clock)
16 Execution timed out 67 ms 33360 KB Time limit exceeded (wall clock)
17 Execution timed out 106 ms 32964 KB Time limit exceeded (wall clock)