oj.uz

Submission #998294

# Submission time Handle Problem Language Result Execution time Memory
998294 2024-06-13T14:14:58 Z BF001 Regions (IOI09_regions) C++17
100 / 100
 2975 ms 128576 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 1 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 4 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 14 ms 8792 KB Output is correct
7 Correct 21 ms 8792 KB Output is correct
8 Correct 19 ms 8880 KB Output is correct
9 Correct 39 ms 9304 KB Output is correct
10 Correct 47 ms 9048 KB Output is correct
11 Correct 92 ms 9304 KB Output is correct
12 Correct 102 ms 9816 KB Output is correct
13 Correct 122 ms 9560 KB Output is correct
14 Correct 185 ms 10072 KB Output is correct
15 Correct 179 ms 12632 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1406 ms 13104 KB Output is correct
2 Correct 1753 ms 11856 KB Output is correct
3 Correct 2414 ms 14800 KB Output is correct
4 Correct 195 ms 10324 KB Output is correct
5 Correct 295 ms 11600 KB Output is correct
6 Correct 493 ms 27512 KB Output is correct
7 Correct 973 ms 31868 KB Output is correct
8 Correct 1012 ms 56508 KB Output is correct
9 Correct 1797 ms 16296 KB Output is correct
10 Correct 2791 ms 128576 KB Output is correct
11 Correct 2975 ms 15696 KB Output is correct
12 Correct 1048 ms 19304 KB Output is correct
13 Correct 1587 ms 19476 KB Output is correct
14 Correct 1785 ms 33344 KB Output is correct
15 Correct 2592 ms 24476 KB Output is correct
16 Correct 2611 ms 29992 KB Output is correct
17 Correct 2484 ms 42792 KB Output is correct