Submission #1130398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130398		xnqs	Regions (IOI09_regions)	C++20	100 / 100	4128 ms	28176 KiB

regions

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>

const int SQRT = 450;
int gs, regions, q;
int region[200005];
int region_norm[25005];
int region_norm_r[SQRT+1];
std::vector<int> by_region[25005];
std::vector<std::vector<int>> adj_list;

std::vector<int> tour;
std::vector<int> tour_by_region[25005];
int tin[200005];
int tout[200005];

int gt_sqrt[SQRT+1][25005];

void dfs1(int k) {
	tour.emplace_back(k);
	tin[k] = tour.size()-1;
	tour_by_region[region[k]].emplace_back(tin[k]);

	for (const auto& i : adj_list[k]) {
		dfs1(i);
	}

	tout[k] = tour.size()-1;
}

void dfs_pre(int k, int reg, int reg_cnt = 0) {
	reg_cnt += (region[k]==reg);
	gt_sqrt[region_norm[reg]][region[k]] += reg_cnt;
	for (const auto& i : adj_list[k]) {
		dfs_pre(i,reg,reg_cnt);
	}
}

int query(int ra, int rb) {
	if (by_region[ra].size() >= SQRT) {
		return gt_sqrt[region_norm[ra]][rb];
	}
	else {
		int ret = 0;
		for (const auto& a : by_region[ra]) {
			ret += std::upper_bound(tour_by_region[rb].begin(),tour_by_region[rb].end(),tout[a])
			     - std::lower_bound(tour_by_region[rb].begin(),tour_by_region[rb].end(),tin[a]);
		}
		return ret;
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);

	std::cin >> gs >> regions >> q;
	adj_list.resize(gs+1);
	for (int i = 1; i <= gs; i++) {
		int p = 0, reg;
		if (i>1) std::cin >> p;
		std::cin >> reg;
		adj_list[p].emplace_back(i);
		region[i] = reg;
		by_region[reg].emplace_back(i);
	}

	dfs1(1);

	int cnt = 0;
	for (int i = 1; i <= regions; i++) {
		if (by_region[i].size() >= SQRT) {
			region_norm[i] = ++cnt;
			region_norm_r[region_norm[i]] = i;
			dfs_pre(1, i);
		}
	}

#ifdef DBG
	for (const auto& i : tour) {
		std::cout << i << " ";
	}
	std::cout << "\n";
	for (int i = 1; i <= regions; i++) {
		std::cout << i << ": ";
		for (const auto& j : tour_by_region[i]) {
			std::cout << j << " ";
		}
		std::cout << "\n";
	}
	for (int i = 1; i <= gs; i++) {
		std::cout << i << ": " << tin[i] << ", " << tout[i] << "\n";
	}
#endif

	while (q--) {
		int ra, rb;
		std::cin >> ra >> rb;
		std::cout << query(ra,rb) << std::endl;
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85