oj.uz

Submission #998181

# Submission time Handle Problem Language Result Execution time Memory
998181 2024-06-13T11:33:51 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 196 ms 34036 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 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 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 6 ms 9816 KB Time limit exceeded (wall clock)
13 Execution timed out 5 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 40 ms 13144 KB Time limit exceeded (wall clock)
2 Execution timed out 32 ms 11608 KB Time limit exceeded (wall clock)
3 Execution timed out 28 ms 15408 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 77 ms 12968 KB Time limit exceeded (wall clock)
7 Execution timed out 88 ms 14192 KB Time limit exceeded (wall clock)
8 Execution timed out 102 ms 22832 KB Time limit exceeded (wall clock)
9 Execution timed out 43 ms 16720 KB Time limit exceeded (wall clock)
10 Execution timed out 196 ms 34036 KB Time limit exceeded (wall clock)
11 Execution timed out 46 ms 16208 KB Time limit exceeded (wall clock)
12 Execution timed out 93 ms 18060 KB Time limit exceeded (wall clock)
13 Execution timed out 46 ms 18512 KB Time limit exceeded (wall clock)
14 Execution timed out 166 ms 19536 KB Time limit exceeded (wall clock)
15 Execution timed out 56 ms 24400 KB Time limit exceeded (wall clock)
16 Execution timed out 49 ms 33316 KB Time limit exceeded (wall clock)
17 Execution timed out 80 ms 33104 KB Time limit exceeded (wall clock)