oj.uz

Submission #998185

# Submission time Handle Problem Language Result Execution time Memory
998185 2024-06-13T11:34:43 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 220 ms 34124 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);
			break;
		}
		cout << res << "\n";
	}

    return 0;
}

Compilation message

regions.cpp: In function 'int find(int, int)':
regions.cpp:31:6: warning: unused variable 'l' [-Wunused-variable]
   31 |  int l = 0, r = rg[typ].size() - 1, rt = 0;
      |      ^
regions.cpp:31:13: warning: unused variable 'r' [-Wunused-variable]
   31 |  int l = 0, r = rg[typ].size() - 1, rt = 0;
      |             ^
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 8792 KB Time limit exceeded (wall clock)
3 Execution timed out 2 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 2 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 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 6 ms 9560 KB Time limit exceeded (wall clock)
14 Execution timed out 10 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 38 ms 13144 KB Time limit exceeded (wall clock)
2 Execution timed out 38 ms 11620 KB Time limit exceeded (wall clock)
3 Execution timed out 23 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 12928 KB Time limit exceeded (wall clock)
7 Execution timed out 88 ms 14028 KB Time limit exceeded (wall clock)
8 Execution timed out 104 ms 22748 KB Time limit exceeded (wall clock)
9 Execution timed out 30 ms 16720 KB Time limit exceeded (wall clock)
10 Execution timed out 177 ms 34124 KB Time limit exceeded (wall clock)
11 Execution timed out 42 ms 16208 KB Time limit exceeded (wall clock)
12 Execution timed out 71 ms 18000 KB Time limit exceeded (wall clock)
13 Execution timed out 46 ms 18512 KB Time limit exceeded (wall clock)
14 Execution timed out 220 ms 19772 KB Time limit exceeded (wall clock)
15 Execution timed out 51 ms 24440 KB Time limit exceeded (wall clock)
16 Execution timed out 75 ms 33476 KB Time limit exceeded (wall clock)
17 Execution timed out 89 ms 33104 KB Time limit exceeded (wall clock)