Submission #1100312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100312	2024-10-13T13:33:35 Z	vjudge1	Regions (IOI09_regions)	C++17	95 / 100	8000 ms	74024 KB

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 = 430;

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[SQ][R];
int any_big[R][SQ];

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);
	
	// 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;
			for (int c1 : people[r1]) {
				for (int c2 : people[r2]) {
					if (dt[c1] <= dt[c2] && dt[c2] <= ft[c1])
						sol++;
				}
			}
			cout << sol << endl;
		}
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8784 KB	Output is correct
2	Correct	2 ms	8784 KB	Output is correct
3	Correct	3 ms	8784 KB	Output is correct
4	Correct	4 ms	8784 KB	Output is correct
5	Correct	7 ms	8796 KB	Output is correct
6	Correct	15 ms	8784 KB	Output is correct
7	Correct	23 ms	8784 KB	Output is correct
8	Correct	27 ms	8784 KB	Output is correct
9	Correct	32 ms	9040 KB	Output is correct
10	Correct	66 ms	9296 KB	Output is correct
11	Correct	134 ms	9296 KB	Output is correct
12	Correct	159 ms	9808 KB	Output is correct
13	Correct	243 ms	9552 KB	Output is correct
14	Correct	621 ms	9808 KB	Output is correct
15	Correct	662 ms	11600 KB	Output is correct

Subtask #2

80.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2459 ms	16720 KB	Output is correct
2	Correct	3010 ms	15440 KB	Output is correct
3	Correct	5617 ms	18256 KB	Output is correct
4	Correct	282 ms	10064 KB	Output is correct
5	Correct	390 ms	11088 KB	Output is correct
6	Correct	592 ms	33608 KB	Output is correct
7	Correct	2459 ms	34376 KB	Output is correct
8	Correct	944 ms	45052 KB	Output is correct
9	Correct	4050 ms	15492 KB	Output is correct
10	Correct	3465 ms	74024 KB	Output is correct
11	Execution timed out	8019 ms	14920 KB	Time limit exceeded
12	Correct	2743 ms	47688 KB	Output is correct
13	Correct	3667 ms	47944 KB	Output is correct
14	Correct	3297 ms	57804 KB	Output is correct
15	Correct	6937 ms	66072 KB	Output is correct
16	Correct	6789 ms	71496 KB	Output is correct
17	Correct	4770 ms	66120 KB	Output is correct