oj.uz

Submission #1100325

# Submission time Handle Problem Language Result Execution time Memory
1100325 2024-10-13T13:46:36 Z Muaath_5 Regions (IOI09_regions) C++17
100 / 100
 7788 ms 79708 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 = 417, CSQ = N / SQ + 1;

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[CSQ][R];
int any_big[R][CSQ];

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);
	
	//cerr << 1ll * N * SQ*10 << ' ' << 1ll * N * CSQ << endl;
	
	// 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;
			// optimize this with sweep-line
			vector<array<int, 2>> evt;
			evt.reserve(people[r1].size() * 2 + people[r2].size());
			for (int c : people[r1]) {
				evt.push_back({dt[c], 1});
				evt.push_back({ft[c], 3});
			}
			for (int c : people[r2]) {
				evt.push_back({dt[c], 2});
			}
			sort(evt.begin(), evt.end());
			int cover = 0;
			for (auto [x, t] : evt) {
				if (t == 1) cover++;
				if (t == 2) sol += cover;
				if (t == 3) cover--;
			}
			cout << sol << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 3 ms 8528 KB Output is correct
4 Correct 5 ms 8528 KB Output is correct
5 Correct 8 ms 8528 KB Output is correct
6 Correct 15 ms 8696 KB Output is correct
7 Correct 27 ms 8528 KB Output is correct
8 Correct 32 ms 8784 KB Output is correct
9 Correct 46 ms 9040 KB Output is correct
10 Correct 82 ms 9040 KB Output is correct
11 Correct 166 ms 9200 KB Output is correct
12 Correct 168 ms 9552 KB Output is correct
13 Correct 252 ms 9040 KB Output is correct
14 Correct 464 ms 9552 KB Output is correct
15 Correct 484 ms 11344 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 18248 KB Output is correct
2 Correct 2081 ms 17168 KB Output is correct
3 Correct 4077 ms 17744 KB Output is correct
4 Correct 458 ms 9552 KB Output is correct
5 Correct 486 ms 10896 KB Output is correct
6 Correct 609 ms 35152 KB Output is correct
7 Correct 2061 ms 36112 KB Output is correct
8 Correct 1068 ms 49172 KB Output is correct
9 Correct 4569 ms 15180 KB Output is correct
10 Correct 2985 ms 79708 KB Output is correct
11 Correct 7788 ms 14484 KB Output is correct
12 Correct 1904 ms 51272 KB Output is correct
13 Correct 2754 ms 51600 KB Output is correct
14 Correct 3022 ms 59624 KB Output is correct
15 Correct 5203 ms 69708 KB Output is correct
16 Correct 4943 ms 75080 KB Output is correct
17 Correct 4451 ms 67916 KB Output is correct