oj.uz

Submission #1100303

# Submission time Handle Problem Language Result Execution time Memory
1100303 2024-10-13T13:19:40 Z vjudge1 Regions (IOI09_regions) C++17
0 / 100
 13 ms 8528 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 = 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;
			cout << i << ' ' << p << endl;
			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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8016 KB Output isn't correct
2 Incorrect 3 ms 8016 KB Output isn't correct
3 Incorrect 3 ms 8016 KB Output isn't correct
4 Incorrect 3 ms 8148 KB Output isn't correct
5 Runtime error 3 ms 8016 KB Execution killed with signal 13
6 Incorrect 4 ms 8272 KB Output isn't correct
7 Incorrect 7 ms 8272 KB Output isn't correct
8 Runtime error 6 ms 8272 KB Execution killed with signal 13
9 Runtime error 7 ms 8528 KB Execution killed with signal 13
10 Runtime error 13 ms 8528 KB Execution killed with signal 13
11 Execution timed out 9 ms 8372 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 8528 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 8240 KB Time limit exceeded (wall clock)
14 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
15 Execution timed out 7 ms 8528 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8 ms 8528 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 8272 KB Time limit exceeded (wall clock)
3 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 8528 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 8528 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
9 Execution timed out 11 ms 8528 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 8528 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 8528 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 8528 KB Time limit exceeded (wall clock)
14 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
15 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)
16 Execution timed out 8 ms 8528 KB Time limit exceeded (wall clock)
17 Execution timed out 9 ms 8528 KB Time limit exceeded (wall clock)