oj.uz

답안 #1100318

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100318 2024-10-13T13:37:40 Z Muaath_5 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 76872 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 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 8528 KB Output is correct
2 Correct 3 ms 8528 KB Output is correct
3 Correct 4 ms 8528 KB Output is correct
4 Correct 4 ms 8676 KB Output is correct
5 Correct 8 ms 8528 KB Output is correct
6 Correct 15 ms 8528 KB Output is correct
7 Correct 27 ms 8528 KB Output is correct
8 Correct 30 ms 8528 KB Output is correct
9 Correct 46 ms 8784 KB Output is correct
10 Correct 81 ms 8784 KB Output is correct
11 Correct 142 ms 9040 KB Output is correct
12 Correct 172 ms 9552 KB Output is correct
13 Correct 275 ms 9040 KB Output is correct
14 Correct 617 ms 9508 KB Output is correct
15 Correct 695 ms 11344 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3222 ms 18348 KB Output is correct
2 Correct 3074 ms 17072 KB Output is correct
3 Correct 5560 ms 17744 KB Output is correct
4 Correct 282 ms 9552 KB Output is correct
5 Correct 385 ms 10832 KB Output is correct
6 Correct 3470 ms 31048 KB Output is correct
7 Correct 3750 ms 11096 KB Output is correct
8 Correct 2300 ms 40524 KB Output is correct
9 Correct 3766 ms 14920 KB Output is correct
10 Execution timed out 8007 ms 18248 KB Time limit exceeded
11 Execution timed out 8016 ms 14160 KB Time limit exceeded
12 Correct 2756 ms 51220 KB Output is correct
13 Correct 3878 ms 51460 KB Output is correct
14 Correct 3469 ms 61240 KB Output is correct
15 Correct 7236 ms 71560 KB Output is correct
16 Correct 7254 ms 76872 KB Output is correct
17 Correct 4826 ms 69704 KB Output is correct