Submission #998285

#	Time	Username	Problem	Language	Result	Execution time	Memory
998285		BF001	Regions (IOI09_regions)	C++17	0 / 100	101 ms	30168 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];
vector<vector<int>> gt;

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

    while (q--){
    	int r1, r2;
    	cin >> r1 >> r2;
    	if (rg[r1].size() > blsiz){
    		cout << gt[idx[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);
    		}
    		cout << res << "\n";
    	}
    }

    return 0;
}     

Compilation message (stderr)

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

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85