oj.uz

Submission #998187

# Submission time Handle Problem Language Result Execution time Memory
998187 2024-06-13T11:35:36 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 181 ms 34120 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;
      |       ~~~~~~~~~~~~~^~~~~~~
regions.cpp:73:13: warning: unused variable 'x' [-Wunused-variable]
   73 |   for (auto x : v[r1]){
      |             ^

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 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 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 5 ms 9748 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 9560 KB Time limit exceeded (wall clock)
14 Execution timed out 9 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 42 ms 13144 KB Time limit exceeded (wall clock)
2 Execution timed out 31 ms 11608 KB Time limit exceeded (wall clock)
3 Execution timed out 31 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 72 ms 12880 KB Time limit exceeded (wall clock)
7 Execution timed out 96 ms 14160 KB Time limit exceeded (wall clock)
8 Execution timed out 105 ms 22860 KB Time limit exceeded (wall clock)
9 Execution timed out 33 ms 16780 KB Time limit exceeded (wall clock)
10 Execution timed out 181 ms 34120 KB Time limit exceeded (wall clock)
11 Execution timed out 37 ms 16208 KB Time limit exceeded (wall clock)
12 Execution timed out 57 ms 18004 KB Time limit exceeded (wall clock)
13 Execution timed out 50 ms 18512 KB Time limit exceeded (wall clock)
14 Execution timed out 162 ms 19536 KB Time limit exceeded (wall clock)
15 Execution timed out 54 ms 24400 KB Time limit exceeded (wall clock)
16 Execution timed out 49 ms 33360 KB Time limit exceeded (wall clock)
17 Execution timed out 88 ms 33104 KB Time limit exceeded (wall clock)