oj.uz

답안 #1100316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100316 2024-10-13T13:36:17 Z vjudge1 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 72180 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 = 455;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7504 KB Output is correct
2 Correct 3 ms 7504 KB Output is correct
3 Correct 4 ms 7504 KB Output is correct
4 Correct 6 ms 7672 KB Output is correct
5 Correct 8 ms 7504 KB Output is correct
6 Correct 18 ms 7504 KB Output is correct
7 Correct 21 ms 7504 KB Output is correct
8 Correct 28 ms 7504 KB Output is correct
9 Correct 38 ms 8012 KB Output is correct
10 Correct 75 ms 8016 KB Output is correct
11 Correct 147 ms 8016 KB Output is correct
12 Correct 146 ms 8620 KB Output is correct
13 Correct 264 ms 8120 KB Output is correct
14 Correct 568 ms 8784 KB Output is correct
15 Correct 646 ms 10320 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2914 ms 17400 KB Output is correct
2 Correct 2890 ms 14160 KB Output is correct
3 Correct 5616 ms 16976 KB Output is correct
4 Correct 276 ms 8784 KB Output is correct
5 Correct 378 ms 9808 KB Output is correct
6 Correct 626 ms 32508 KB Output is correct
7 Correct 2989 ms 33104 KB Output is correct
8 Correct 981 ms 48088 KB Output is correct
9 Correct 3696 ms 14160 KB Output is correct
10 Execution timed out 8010 ms 70728 KB Time limit exceeded
11 Execution timed out 8041 ms 13436 KB Time limit exceeded
12 Correct 2584 ms 48456 KB Output is correct
13 Correct 3824 ms 48828 KB Output is correct
14 Correct 3322 ms 58588 KB Output is correct
15 Correct 6985 ms 66864 KB Output is correct
16 Correct 7344 ms 72180 KB Output is correct
17 Correct 5465 ms 67116 KB Output is correct