oj.uz

Submission #998292

# Submission time Handle Problem Language Result Execution time Memory
998292 2024-06-13T14:11:41 Z BF001 Regions (IOI09_regions) C++17
100 / 100
 2971 ms 128424 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] << endl;
    	}
    	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 << endl;
    	}
    }

    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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 11 ms 8792 KB Output is correct
7 Correct 16 ms 8792 KB Output is correct
8 Correct 18 ms 8792 KB Output is correct
9 Correct 30 ms 9264 KB Output is correct
10 Correct 54 ms 9048 KB Output is correct
11 Correct 74 ms 9304 KB Output is correct
12 Correct 119 ms 9816 KB Output is correct
13 Correct 128 ms 9560 KB Output is correct
14 Correct 185 ms 10072 KB Output is correct
15 Correct 224 ms 12596 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1518 ms 13096 KB Output is correct
2 Correct 1752 ms 11864 KB Output is correct
3 Correct 2433 ms 14840 KB Output is correct
4 Correct 192 ms 10072 KB Output is correct
5 Correct 302 ms 11608 KB Output is correct
6 Correct 461 ms 27412 KB Output is correct
7 Correct 975 ms 31860 KB Output is correct
8 Correct 992 ms 56508 KB Output is correct
9 Correct 1812 ms 16208 KB Output is correct
10 Correct 2786 ms 128424 KB Output is correct
11 Correct 2971 ms 15544 KB Output is correct
12 Correct 1117 ms 19304 KB Output is correct
13 Correct 1551 ms 19644 KB Output is correct
14 Correct 1825 ms 33144 KB Output is correct
15 Correct 2667 ms 24476 KB Output is correct
16 Correct 2610 ms 29832 KB Output is correct
17 Correct 2532 ms 42812 KB Output is correct