oj.uz

Submission #1100310

# Submission time Handle Problem Language Result Execution time Memory
1100310 2024-10-13T13:29:55 Z vjudge1 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 71496 KB 
// 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;

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 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++;
			
			int fakelazy[N] = {};
			// 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 3 ms 8272 KB Output is correct
2 Correct 3 ms 8272 KB Output is correct
3 Correct 4 ms 8272 KB Output is correct
4 Correct 7 ms 8272 KB Output is correct
5 Correct 8 ms 8272 KB Output is correct
6 Correct 13 ms 8272 KB Output is correct
7 Correct 22 ms 8272 KB Output is correct
8 Correct 25 ms 8272 KB Output is correct
9 Correct 36 ms 8784 KB Output is correct
10 Correct 77 ms 8784 KB Output is correct
11 Correct 153 ms 8784 KB Output is correct
12 Correct 156 ms 9296 KB Output is correct
13 Correct 242 ms 9040 KB Output is correct
14 Correct 530 ms 9552 KB Output is correct
15 Correct 571 ms 11088 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2444 ms 18248 KB Output is correct
2 Correct 3301 ms 14928 KB Output is correct
3 Correct 6387 ms 17744 KB Output is correct
4 Correct 288 ms 9552 KB Output is correct
5 Correct 392 ms 10576 KB Output is correct
6 Correct 579 ms 31224 KB Output is correct
7 Correct 2269 ms 33864 KB Output is correct
8 Correct 917 ms 44616 KB Output is correct
9 Correct 4168 ms 14928 KB Output is correct
10 Correct 3941 ms 71496 KB Output is correct
11 Execution timed out 8053 ms 14412 KB Time limit exceeded
12 Correct 2826 ms 47104 KB Output is correct
13 Correct 4038 ms 47432 KB Output is correct
14 Correct 3659 ms 55256 KB Output is correct
15 Correct 7031 ms 63520 KB Output is correct
16 Correct 6920 ms 68936 KB Output is correct
17 Correct 4927 ms 63636 KB Output is correct