Submission #1100316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100316	2024-10-13T13:36:17 Z	vjudge1	Regions (IOI09_regions)	C++17	90 / 100	8000 ms	72180 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 = 455;

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	7504 KB	Output is correct
2	Correct	3 ms	7504 KB	Output is correct
3	Correct	4 ms	7504 KB	Output is correct
4	Correct	6 ms	7672 KB	Output is correct
5	Correct	8 ms	7504 KB	Output is correct
6	Correct	18 ms	7504 KB	Output is correct
7	Correct	21 ms	7504 KB	Output is correct
8	Correct	28 ms	7504 KB	Output is correct
9	Correct	38 ms	8012 KB	Output is correct
10	Correct	75 ms	8016 KB	Output is correct
11	Correct	147 ms	8016 KB	Output is correct
12	Correct	146 ms	8620 KB	Output is correct
13	Correct	264 ms	8120 KB	Output is correct
14	Correct	568 ms	8784 KB	Output is correct
15	Correct	646 ms	10320 KB	Output is correct

Subtask #2

75.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2914 ms	17400 KB	Output is correct
2	Correct	2890 ms	14160 KB	Output is correct
3	Correct	5616 ms	16976 KB	Output is correct
4	Correct	276 ms	8784 KB	Output is correct
5	Correct	378 ms	9808 KB	Output is correct
6	Correct	626 ms	32508 KB	Output is correct
7	Correct	2989 ms	33104 KB	Output is correct
8	Correct	981 ms	48088 KB	Output is correct
9	Correct	3696 ms	14160 KB	Output is correct
10	Execution timed out	8010 ms	70728 KB	Time limit exceeded
11	Execution timed out	8041 ms	13436 KB	Time limit exceeded
12	Correct	2584 ms	48456 KB	Output is correct
13	Correct	3824 ms	48828 KB	Output is correct
14	Correct	3322 ms	58588 KB	Output is correct
15	Correct	6985 ms	66864 KB	Output is correct
16	Correct	7344 ms	72180 KB	Output is correct
17	Correct	5465 ms	67116 KB	Output is correct