Submission #492344

#	Time	Username	Problem	Language	Result	Execution time	Memory
492344		keta_tsimakuridze	Regions (IOI09_regions)	C++14	100 / 100	7400 ms	105772 KiB

regions

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, Bl = 400, n, r, q, c[N],idx = 0, tmin[N], tmout[N], id[N];
vector<int> heavy_p[25005], V[N];
vector<int> comp[N], x;
set<pii> occ[N];
void dfs(int u,int p) {
	tmin[u] = ++t;
	x[id[c[u]]]++;occ[c[u]].insert({tmin[u], occ[c[u]].size()});
	for(int i = 0; i < V[u].size(); i++) {
		dfs(V[u][i], u);
	}
	x[id[c[u]]]--;
	for(int i = 0; i < x.size(); i++) {
		heavy_p[c[u]][i] += x[i];
	}
	
	tmout[u] = t;
}
main(){
	cin >> n >> r >> q;
	cin >> c[1];
	for(int i = 2; i <= n; i++) {
		int p;
		cin >> p >> c[i];
		V[p].push_back(i);
	}
	for(int i = 1; i <= n; i++) {
		comp[c[i]].push_back(i);
	}
	idx = 0;
	for(int i = 1; i <= r; i++) {
		if(comp[i].size() >= Bl) {
			id[i] = ++idx;
		}
	}
	for(int i = 1; i <= r; i++) {
		heavy_p[i].resize(n/Bl + 2);
		occ[i].insert({0, 0});
	}
	x.resize(n/Bl + 2);
	dfs(1, 0);
	for(int i = 1; i <= r; i++) {
		occ[i].insert({n + 1, occ[i].size()});
	}
	while(q--) {
		int r1,r2;
		cin >> r1 >> r2;
		if(comp[r1].size() >= Bl) {
			cout << heavy_p[r2][id[r1]] << endl;
		}
		else {
			int ans = 0;
			for(int i = 0; i < comp[r1].size(); i++) {
				int l = tmin[comp[r1][i]], r = tmout[comp[r1][i]];
				ans += ((*occ[r2].upper_bound({r, n + 1})).s - 1 - (*--occ[r2].upper_bound({l - 1, n + 1})).s);
			}
			cout << ans << endl;
		}
	}
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
regions.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if(comp[i].size() >= Bl) {
      |      ~~~~~~~~~~~~~~~^~~~~
regions.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |   if(comp[r1].size() >= Bl) {
      |      ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int i = 0; i < comp[r1].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

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