Submission #1100318

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100318	2024-10-13T13:37:40 Z	Muaath_5	Regions (IOI09_regions)	C++17	90 / 100	8000 ms	76872 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 = 500;

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	8528 KB	Output is correct
2	Correct	3 ms	8528 KB	Output is correct
3	Correct	4 ms	8528 KB	Output is correct
4	Correct	4 ms	8676 KB	Output is correct
5	Correct	8 ms	8528 KB	Output is correct
6	Correct	15 ms	8528 KB	Output is correct
7	Correct	27 ms	8528 KB	Output is correct
8	Correct	30 ms	8528 KB	Output is correct
9	Correct	46 ms	8784 KB	Output is correct
10	Correct	81 ms	8784 KB	Output is correct
11	Correct	142 ms	9040 KB	Output is correct
12	Correct	172 ms	9552 KB	Output is correct
13	Correct	275 ms	9040 KB	Output is correct
14	Correct	617 ms	9508 KB	Output is correct
15	Correct	695 ms	11344 KB	Output is correct

Subtask #2

75.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3222 ms	18348 KB	Output is correct
2	Correct	3074 ms	17072 KB	Output is correct
3	Correct	5560 ms	17744 KB	Output is correct
4	Correct	282 ms	9552 KB	Output is correct
5	Correct	385 ms	10832 KB	Output is correct
6	Correct	3470 ms	31048 KB	Output is correct
7	Correct	3750 ms	11096 KB	Output is correct
8	Correct	2300 ms	40524 KB	Output is correct
9	Correct	3766 ms	14920 KB	Output is correct
10	Execution timed out	8007 ms	18248 KB	Time limit exceeded
11	Execution timed out	8016 ms	14160 KB	Time limit exceeded
12	Correct	2756 ms	51220 KB	Output is correct
13	Correct	3878 ms	51460 KB	Output is correct
14	Correct	3469 ms	61240 KB	Output is correct
15	Correct	7236 ms	71560 KB	Output is correct
16	Correct	7254 ms	76872 KB	Output is correct
17	Correct	4826 ms	69704 KB	Output is correct