oj.uz

Submission #1100304

# Submission time Handle Problem Language Result Execution time Memory
1100304 2024-10-13T13:22:43 Z vjudge1 Regions (IOI09_regions) C++17
30 / 100
 8000 ms 71752 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 = 450;

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 << big_any[idx[r1]][r2] << endl;
		else if (type[r2]) cout << 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 9296 KB Output is correct
2 Correct 2 ms 9296 KB Output is correct
3 Correct 3 ms 9400 KB Output is correct
4 Correct 6 ms 9296 KB Output is correct
5 Correct 7 ms 9296 KB Output is correct
6 Correct 15 ms 9296 KB Output is correct
7 Correct 22 ms 9296 KB Output is correct
8 Correct 23 ms 9296 KB Output is correct
9 Correct 37 ms 9808 KB Output is correct
10 Correct 71 ms 9808 KB Output is correct
11 Correct 137 ms 9808 KB Output is correct
12 Correct 150 ms 10320 KB Output is correct
13 Correct 234 ms 9808 KB Output is correct
14 Correct 549 ms 10320 KB Output is correct
15 Correct 558 ms 12112 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2514 ms 19024 KB Output isn't correct
2 Incorrect 2850 ms 17744 KB Output isn't correct
3 Incorrect 5653 ms 20560 KB Output isn't correct
4 Correct 296 ms 10320 KB Output is correct
5 Correct 376 ms 11600 KB Output is correct
6 Incorrect 574 ms 33864 KB Output isn't correct
7 Incorrect 2794 ms 34640 KB Output isn't correct
8 Incorrect 943 ms 47260 KB Output isn't correct
9 Correct 3852 ms 15440 KB Output is correct
10 Incorrect 7413 ms 71752 KB Output isn't correct
11 Execution timed out 8006 ms 14748 KB Time limit exceeded
12 Incorrect 2643 ms 49480 KB Output isn't correct
13 Incorrect 3781 ms 49704 KB Output isn't correct
14 Incorrect 3402 ms 57604 KB Output isn't correct
15 Incorrect 7185 ms 65884 KB Output isn't correct
16 Incorrect 7222 ms 71320 KB Output isn't correct
17 Incorrect 4974 ms 66048 KB Output isn't correct