Submission #998272

#	Time	Username	Problem	Language	Result	Execution time	Memory
998272		BF001	Regions (IOI09_regions)	C++17	0 / 100	206 ms	77036 KiB

regions

#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define M 25005 

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

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

void dfs(int u, int typ, int cnt){
	int ncnt = cnt;
	if (h[u] == typ) ncnt++;
	for (auto x : adj[u]){
		gt[idx[typ]][h[x]] += ncnt;
		dfs(x, typ, ncnt);
	} 	
}

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

	blsiz = sqrt(n);

	gt.resize(blsiz + 1);
	for(int i = 0; i <= blsiz; i++) gt[i].resize(r + 1);

	init(1);
	for (int i = 1; i <= r; i++){
		if (rg[i].size() < blsiz) continue;
		idx[i] = ++cnt;
		dfs(1, i, 0);
	}

	for (int i = 1; i <= q; i++){
		int r1, r2;
		cin >> r1 >> r2;
		if (rg[r1].size() >= blsiz){
			cout << gt[idx[r1]][r2] << "\n";
			
			continue;
		}
		int res = 0;
		for (auto x : v[r1]){
			res += find(r2, tout[x]) - find(r2, tin[x] - 1);
			break;
		}
		cout << res << "\n";
	}

    return 0;
}     

Compilation message (stderr)

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

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