oj.uz

Submission #1100298

# Submission time Handle Problem Language Result Execution time Memory
1100298 2024-10-13T12:57:58 Z vjudge1 Regions (IOI09_regions) C++17
35 / 100
 8000 ms 75080 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 = 500;

int n, r, q, reg[N];
vector<int> adj[N];
vector<int> people[R];

// dfs tree
int ttt = 0, 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]) {
		dfs(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];
				big_any[idx[i]][reg[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 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 4 ms 7248 KB Output is correct
4 Correct 5 ms 7248 KB Output is correct
5 Correct 8 ms 7248 KB Output is correct
6 Correct 16 ms 7504 KB Output is correct
7 Correct 26 ms 7504 KB Output is correct
8 Correct 20 ms 7504 KB Output is correct
9 Correct 33 ms 7760 KB Output is correct
10 Correct 80 ms 7760 KB Output is correct
11 Correct 140 ms 8016 KB Output is correct
12 Correct 150 ms 8272 KB Output is correct
13 Correct 244 ms 8016 KB Output is correct
14 Correct 557 ms 8612 KB Output is correct
15 Correct 574 ms 10320 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2764 ms 16976 KB Output isn't correct
2 Incorrect 2816 ms 15900 KB Output isn't correct
3 Incorrect 5663 ms 18256 KB Output isn't correct
4 Correct 268 ms 8528 KB Output is correct
5 Correct 370 ms 9808 KB Output is correct
6 Incorrect 3491 ms 30032 KB Output isn't correct
7 Correct 3620 ms 10064 KB Output is correct
8 Incorrect 2339 ms 38472 KB Output isn't correct
9 Correct 3779 ms 14152 KB Output is correct
10 Execution timed out 8058 ms 17468 KB Time limit exceeded
11 Execution timed out 8003 ms 13388 KB Time limit exceeded
12 Incorrect 2666 ms 52296 KB Output isn't correct
13 Incorrect 3586 ms 52040 KB Output isn't correct
14 Incorrect 3326 ms 62204 KB Output isn't correct
15 Incorrect 6794 ms 71568 KB Output isn't correct
16 Incorrect 6786 ms 75080 KB Output isn't correct
17 Incorrect 4800 ms 68168 KB Output isn't correct