Submission #998294

#	Time	Username	Problem	Language	Result	Execution time	Memory
998294		BF001	Regions (IOI09_regions)	C++17	100 / 100	2975 ms	128576 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85