Submission #556317

#	Time	Username	Problem	Language	Result	Execution time	Memory
556317		GioChkhaidze	Regions (IOI09_regions)	C++14	100 / 100	3822 ms	75084 KiB

regions

#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 2e5 + 5;
const int M = 25005;

int sq;
bool Hv[M], Lh[M];
int n, r, q, timer;
vector < int > s, v[N], R[M];
int in[N], out[N], O[N], c[N], p[N], idx[M], G[M][500], cur[500];

bool is_anc(int a, int b) {
	return (in[a] <= in[b] && out[b] <= out[a]);
}

void dfs(int x) {
	in[x] = ++timer;
	O[timer] = x;
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		dfs(to);  
	}
	out[x] = timer;
}

void wfs(int x) {
	int col = c[x];
	for (int i = 0; i < s.size(); ++i) {
		if (col == s[i]) continue;
		G[col][i] += cur[i];
	}
	
	if (Hv[col]) {
		++cur[idx[col]];
	}

	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		wfs(to);  
	}
	
	if (Hv[col]) {
		--cur[idx[col]];
	}
}

main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> r >> q;
	cin >> c[1];
	for (int i = 2; i <= n; ++i) {
		cin >> p[i] >> c[i];
		v[p[i]].pb(i);
	}
	
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		R[c[i]].pb(in[i]);
	}
	
	sq = sqrt(n);
	for (int i = 1; i <= r; ++i) {
		sort(R[i].begin(), R[i].end());
		if (R[i].size() > sq) {
			idx[i] = s.size();
			Hv[i] = true;
			s.pb(i);	
		}
			else {
			Lh[i] = true;
		}
	}
	
	wfs(1);
	for (int i = 1; i <= q; ++i) {
		int x, y, ans = 0;
		cin >> x >> y;
		if (Lh[x]) {
			for (int j = 0; j < R[x].size(); ++j) {
				int id = O[R[x][j]];
				int Rc = (lower_bound(R[y].begin(), R[y].end(), out[id] + 1) - R[y].begin());
				int Lc = (lower_bound(R[y].begin(), R[y].end(), in[id]) - R[y].begin());
				ans += Rc - Lc;
			}
		}
			else {
			ans = G[y][idx[x]];
		}
		cout << ans << endl;	
	} 
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void wfs(int)':
regions.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
regions.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main () {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:71:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   if (R[i].size() > sq) {
      |       ~~~~~~~~~~~~^~~~
regions.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int j = 0; j < R[x].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~

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