oj.uz

답안 #1100312

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

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 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 3 ms 8784 KB Output is correct
4 Correct 4 ms 8784 KB Output is correct
5 Correct 7 ms 8796 KB Output is correct
6 Correct 15 ms 8784 KB Output is correct
7 Correct 23 ms 8784 KB Output is correct
8 Correct 27 ms 8784 KB Output is correct
9 Correct 32 ms 9040 KB Output is correct
10 Correct 66 ms 9296 KB Output is correct
11 Correct 134 ms 9296 KB Output is correct
12 Correct 159 ms 9808 KB Output is correct
13 Correct 243 ms 9552 KB Output is correct
14 Correct 621 ms 9808 KB Output is correct
15 Correct 662 ms 11600 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2459 ms 16720 KB Output is correct
2 Correct 3010 ms 15440 KB Output is correct
3 Correct 5617 ms 18256 KB Output is correct
4 Correct 282 ms 10064 KB Output is correct
5 Correct 390 ms 11088 KB Output is correct
6 Correct 592 ms 33608 KB Output is correct
7 Correct 2459 ms 34376 KB Output is correct
8 Correct 944 ms 45052 KB Output is correct
9 Correct 4050 ms 15492 KB Output is correct
10 Correct 3465 ms 74024 KB Output is correct
11 Execution timed out 8019 ms 14920 KB Time limit exceeded
12 Correct 2743 ms 47688 KB Output is correct
13 Correct 3667 ms 47944 KB Output is correct
14 Correct 3297 ms 57804 KB Output is correct
15 Correct 6937 ms 66072 KB Output is correct
16 Correct 6789 ms 71496 KB Output is correct
17 Correct 4770 ms 66120 KB Output is correct