Submission #1202054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202054		NikoBaotic	Regions (IOI09_regions)	C++20	100 / 100	7893 ms	26768 KiB

regions

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 200100;
const int R1 = 510;
const int R2 = 25010;

int n, r, q;
int h[N];
int par[N];
vector<int> chi[N];
vector<int> emp[R2];
vector<pii> empIn[R2];
vector<pii> empOut[R2];
int in[N];
int out[N];
int timer;
int cnt[R1][R1];

vector<int>* dfs(int node) {
	vector<int>* cur = nullptr;

	for (int u : chi[node]) {
		vector<int>* v = dfs(u);

		if (cur == nullptr) {
			cur = v;
		} else {
			for (int i = 1; i < R1; i++) {
				(*cur)[i] += (*v)[i];
			}

			delete(v);
		}
	}
	
	if (sz(chi[node]) == 0) {
		cur = new vector<int>(R1);
	}
	
	for (int i = 1; i < R1; i++) {
		cnt[h[node]][i] += (*cur)[i];
	}

	(*cur)[h[node]]++;

	return cur;
}

void dfs2(int node) {
	timer++;
	in[node] = timer;

	for (int u : chi[node]) {
		dfs2(u);
	}

	out[node] = timer;
}

int main() {
	scanf("%d%d%d", &n, &r, &q);
	
	for (int i = 1; i <= n; i++) {
		if (i != 1) {
			scanf("%d", &par[i]);

			chi[par[i]].pb(i);
		}

		scanf("%d", &h[i]);
		emp[h[i]].pb(i);
	}

	if (r <= 500) {
		dfs(1);

		for (int i = 0; i < q; i++) {
			int r1, r2;
			scanf("%d%d", &r1, &r2);

			int ans = cnt[r1][r2];

			printf("%d\n", ans);
			fflush(stdout);
		}
	} else {
		dfs2(1);

		for (int i = 1; i <= n; i++) {
			empIn[h[i]].pb({in[i], i});
			empOut[h[i]].pb({out[i], i});
		}

		for (int i = 1; i <= r; i++) {
			sort(all(empIn[i]));
			sort(all(empOut[i]));
		}

		for (int i = 0; i < q; i++) {
			int r1, r2;
			scanf("%d%d", &r1, &r2);

			int ptrR2 = 0;
			int ptrIn = 0;
			int ptrOut = 0;

			int sum = 0;
			int ans = 0;

			while (ptrIn < sz(empIn[r1]) or ptrOut < sz(empOut[r1])) {
				int curIn = INT_MAX;
				int curOut = INT_MAX;
				int curR2 = INT_MAX;

				if (ptrIn < sz(empIn[r1])) curIn = empIn[r1][ptrIn].F - 1;
				if (ptrOut < sz(empOut[r1])) curOut = empOut[r1][ptrOut].F;
				if (ptrR2 < sz(empIn[r2])) curR2 = empIn[r2][ptrR2].F;

				int cur = min({curIn, curOut, curR2});

				while (ptrR2 < sz(empIn[r2]) and cur >= empIn[r2][ptrR2].F) {
					sum++;
					ptrR2++;
				}

				while (ptrIn < sz(empIn[r1]) and cur >= empIn[r1][ptrIn].F - 1) {
					ans -= sum;
					ptrIn++;
				}
				
				while (ptrOut < sz(empOut[r1]) and cur >= empOut[r1][ptrOut].F) {
					ans += sum;
					ptrOut++;
				}
			}	
			
			printf("%d\n", ans);
			fflush(stdout);
		}
	}

	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d%d", &n, &r, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:77:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |                         scanf("%d", &par[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~
regions.cpp:82:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |                 scanf("%d", &h[i]);
      |                 ~~~~~^~~~~~~~~~~~~
regions.cpp:91:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |                         scanf("%d%d", &r1, &r2);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:113:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |                         scanf("%d%d", &r1, &r2);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~

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