oj.uz

Submission #998286

# Submission time Handle Problem Language Result Execution time Memory
998286 2024-06-13T13:59:43 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 440 ms 128648 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define M 25005

int n, r, q, tim, tin[N], tout[N], vs[M], node[N], h[N], idx[M], cnt = -1;
vector<int> adj[N], rg[M];
unordered_map<int, int> gt[M];

void init(int u, int p){
	tin[u] = ++tim;
	rg[h[u]].push_back(tin[u]);
	node[tim] = u;
	for (auto x : adj[u]){
		if (x == p) continue;
		init(x, u);
	}
	tout[u] = tim;
}

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);
    }

    init(1, 0);
    const int blsiz = sqrt(n);

    for (int i = 1; i <= n; i++){
    	if (vs[h[node[i]]]) continue;
    	vs[h[node[i]]] = 1;
    	if (rg[h[node[i]]].size() <= blsiz) continue;
    	vector<int> pre(n + 2, 0);
    	for (auto x : rg[h[node[i]]]){
    		int l = tin[node[x]], r = tout[node[x]];
    		pre[l]++; pre[r + 1]--;
    	}
    	for (int j = 1; j <= n; j++){
    		pre[j] += pre[j - 1];
    		gt[h[node[i]]][h[node[j]]] += pre[j];  
    	}
    }

    while (q--){
    	int r1, r2;
    	cin >> r1 >> r2;
    	if (rg[r1].size() > blsiz){
    		cout << gt[r1][r2] << "\n";
    	}
    	else {
    		int res = 0;
    		for (auto x : rg[r1]){
    			int l = tin[node[x]], r = tout[node[x]];
    			res += find(r2, r) - find(r2, l - 1);
    		}
    		cout << res << "\n";
    	}
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:54:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   54 |      if (rg[h[node[i]]].size() <= blsiz) continue;
      |          ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
regions.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   69 |      if (rg[r1].size() > blsiz){
      |          ~~~~~~~~~~~~~~^~~~~~~

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 9044 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 3 ms 8792 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 9304 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 9048 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 9300 KB Time limit exceeded (wall clock)
12 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 9560 KB Time limit exceeded (wall clock)
14 Execution timed out 7 ms 10072 KB Time limit exceeded (wall clock)
15 Execution timed out 9 ms 12632 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 24 ms 13184 KB Time limit exceeded (wall clock)
2 Execution timed out 20 ms 11864 KB Time limit exceeded (wall clock)
3 Execution timed out 20 ms 14840 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 10072 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 11608 KB Time limit exceeded (wall clock)
6 Execution timed out 63 ms 27512 KB Time limit exceeded (wall clock)
7 Execution timed out 82 ms 31812 KB Time limit exceeded (wall clock)
8 Execution timed out 182 ms 56216 KB Time limit exceeded (wall clock)
9 Execution timed out 33 ms 16216 KB Time limit exceeded (wall clock)
10 Execution timed out 440 ms 128648 KB Time limit exceeded (wall clock)
11 Execution timed out 54 ms 15696 KB Time limit exceeded (wall clock)
12 Execution timed out 74 ms 19252 KB Time limit exceeded (wall clock)
13 Execution timed out 43 ms 19560 KB Time limit exceeded (wall clock)
14 Execution timed out 119 ms 33316 KB Time limit exceeded (wall clock)
15 Execution timed out 46 ms 24420 KB Time limit exceeded (wall clock)
16 Execution timed out 70 ms 29832 KB Time limit exceeded (wall clock)
17 Execution timed out 119 ms 42820 KB Time limit exceeded (wall clock)