Submission #366883

#	Time	Username	Problem	Language	Result	Execution time	Memory
366883		kostia244	Regions (IOI09_regions)	C++17	100 / 100	6462 ms	41832 KiB

regions

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn = 2e5 + 5, C = 300;
using ll = long long;
int n, r, q, tin[maxn], tout[maxn], col[maxn], col_cnt[maxn], heavy_id[maxn], heavy_cnt = 0, timer = 0;
vector<int> g[maxn], col_list[maxn];
vector<int> col_tin[maxn], col_tout[maxn];
void dfs(int v) {
	tin[v] = timer++;
	for(int i : g[v]) dfs(i);
	tout[v] = timer;
}
//A[bottom][top]
ll A[maxn/C + 1][maxn/C + 1], par_cols[maxn];
 
void count_heavy(int v) {
	if(heavy_id[col[v]] >= 0) {
		par_cols[heavy_id[col[v]]]++;
		A[heavy_id[col[v]]][heavy_id[col[v]]]--;
		for(int i = 0; i < heavy_cnt; i++)
			A[heavy_id[col[v]]][i] += par_cols[i];
	}
	for(int i : g[v]) {
		count_heavy(i);
	}
	if(heavy_id[col[v]] >= 0) par_cols[heavy_id[col[v]]]--;
}
void count_light() {
	for(int i = 0; i < r; i++) {
		vector<int> &tins = col_tin[i], &touts = col_tout[i];
		for(auto v : col_list[i]) tins.push_back(tin[v]), touts.push_back(tout[v]);
		sort(all(tins));
		sort(all(touts));
	}
}
int lower_bound(vector<int> &a, int x) {
	int as = a.size(), i = -1;
	for(int z = 1<<18; z>>=1;)
		i += z*(i+z < as && a[i+z] <= x);
	return i+1;
}
ll count_top(int r1, int r2) {
	ll ans = 0;
	for(auto i : col_list[r1]) {
		ans += lower_bound(col_tin[r2], tout[i]-1) - lower_bound(col_tin[r2], tin[i]-1);
	}
	return ans;
}
ll count_bottom(int r1, int r2) {
	ll ans = 0;
	//cout << "Uh " << col_list[r2].size() << " v " << col_list[r1].size() << endl;
	for(auto i : col_list[r2]) {
		ans += lower_bound(col_tin[r1], tin[i]) - lower_bound(col_tout[r1], tin[i]);
		//cout << lower_bound(col_tin[r1], tin[i]) << " | " << lower_bound(col_tout[r1], tin[i]) << endl;
	}
	return ans;
}
ll count_linear(int r1, int r2) {
	if(col_cnt[r1] < col_cnt[r2]) return count_top(r1, r2);
	return count_bottom(r1, r2);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> r >> q;
	for(int t, i = 0; i < n; i++) {
		if(i) cin >> t, t--, g[t].push_back(i);
		cin >> col[i];col[i]--;
		col_cnt[col[i]]++;
		col_list[col[i]].push_back(i);
		
	}
	memset(heavy_id, -1, sizeof heavy_id);
	dfs(0);
	for(int i = 0; i < r; i++) if(col_cnt[i] > C) {
		heavy_id[i] = heavy_cnt++;
	}
	count_heavy(0);
	count_light();
	/*
	for(auto i : col_tin[0]) cout << i << " "; cout << endl;
	for(auto i : col_tout[0]) cout << i << " "; cout << endl;
	for(auto i : col_tin[1]) cout << i << " "; cout << endl;
	for(auto i : col_tout[1]) cout << i << " "; cout << endl;
	*/
	for(int r1, r2; q--; cout << endl) {
		cin >> r1 >> r2; --r1, --r2;
		if(min(heavy_id[r1], heavy_id[r2]) >= 0) {
			cout << A[heavy_id[r2]][heavy_id[r1]];
          	continue;
		}
		//cout << r1 << " " << r2 << "uwu" << endl;
		cout << count_linear(r1, r2);
	}
}

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