Submission #1100326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100326		vjudge1	Regions (IOI09_regions)	C++17	100 / 100	7662 ms	79716 KiB

regions

// Problem: D - Regions
// Contest: Virtual Judge - 2024-10-13 - 10/10 problems
// URL: https://vjudge.net/contest/661996#problem/D
// Memory Limit: 128 MB
// Time Limit: 8000 ms
// 
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5+1, R = 25001, SQ = 417, CSQ = N / SQ + 1;

int n, r, q, reg[N];
vector<int> adj[N];
vector<int> people[R];

// dfs tree
int ttt = 1, dt[N], ft[N];
void dfs(int node) {
	dt[node] = ttt++;
	for (int ch : adj[node]) {
		dfs(ch);
	}
	ft[node] = ttt-1;
}

// small & big
int type[R]; // boolean 0=small, 1=big
int idx[R];

int big_any[CSQ][R];
int any_big[R][CSQ];

int srch = 0;
int sum[N];
void dfs2(int node) {
	sum[node] = (reg[node] == srch);
	for (int ch : adj[node]) {
		dfs2(ch);
		sum[node] += sum[ch];
	}
}
int fakelazy[N] = {};
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> r >> q;
	for (int i = 1; i <= n; i++) {
		if (i != 1) {
			int p;
			cin >> p;
			adj[p].push_back(i);
		}
		cin >> reg[i];
		people[reg[i]].push_back(i);
	}
	dfs(1);
	
	//cerr << 1ll * N * SQ*10 << ' ' << 1ll * N * CSQ << endl;
	
	// precalc
	int lstidx = 0;
	for (int i = 1; i <= r; i++) {
		type[i] = (people[i].size() >= SQ);
		if (type[i]) {
			idx[i] = lstidx++;
			
			memset(fakelazy, 0, sizeof(fakelazy));
			// precalculate
			
			// big_any
			for (int c : people[i]) {
				fakelazy[dt[c]]++;
				fakelazy[ft[c]+1]--;
			}
			for (int j = 1; j <= n; j++)
				fakelazy[j] += fakelazy[j-1];
			for (int j = 1; j <= n; j++)
				big_any[idx[i]][reg[j]] += fakelazy[dt[j]];
			
			
			// any_big
			srch = i;
			dfs2(1);
			
			for (int j = 1; j <= n; j++)
				any_big[reg[j]][idx[i]] += sum[j];
		}
	}
	
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		if (type[r1]) cout
		#ifdef MUAATH_5
		<< '#'
		#endif
		<< big_any[idx[r1]][r2] << endl;
		else if (type[r2]) cout 
		#ifdef MUAATH_5
		<< '*'
		#endif
		<< any_big[r1][idx[r2]] << endl;
		else {
			int sol = 0;
			// optimize this with sweep-line
			vector<array<int, 2>> evt;
			evt.reserve(people[r1].size() * 2 + people[r2].size());
			for (int c : people[r1]) {
				evt.push_back({dt[c], 1});
				evt.push_back({ft[c], 3});
			}
			for (int c : people[r2]) {
				evt.push_back({dt[c], 2});
			}
			sort(evt.begin(), evt.end());
			int cover = 0;
			for (auto [x, t] : evt) {
				if (t == 1) cover++;
				if (t == 2) sol += cover;
				if (t == 3) cover--;
			}
			cout << sol << endl;
		}
	}
}

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