Submission #366883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366883	2021-02-15T15:57:12 Z	kostia244	Regions (IOI09_regions)	C++17	100 / 100	6462 ms	41832 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	19948 KB	Output is correct
2	Correct	16 ms	19948 KB	Output is correct
3	Correct	19 ms	19948 KB	Output is correct
4	Correct	18 ms	19948 KB	Output is correct
5	Correct	23 ms	19948 KB	Output is correct
6	Correct	38 ms	20076 KB	Output is correct
7	Correct	37 ms	20076 KB	Output is correct
8	Correct	41 ms	20076 KB	Output is correct
9	Correct	57 ms	20460 KB	Output is correct
10	Correct	131 ms	20588 KB	Output is correct
11	Correct	175 ms	20844 KB	Output is correct
12	Correct	201 ms	21356 KB	Output is correct
13	Correct	270 ms	21100 KB	Output is correct
14	Correct	401 ms	21740 KB	Output is correct
15	Correct	482 ms	24300 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2543 ms	25068 KB	Output is correct
2	Correct	2585 ms	23916 KB	Output is correct
3	Correct	4217 ms	26836 KB	Output is correct
4	Correct	276 ms	21868 KB	Output is correct
5	Correct	401 ms	23404 KB	Output is correct
6	Correct	626 ms	23548 KB	Output is correct
7	Correct	1738 ms	24684 KB	Output is correct
8	Correct	1254 ms	30060 KB	Output is correct
9	Correct	2777 ms	30828 KB	Output is correct
10	Correct	4962 ms	36332 KB	Output is correct
11	Correct	6462 ms	31212 KB	Output is correct
12	Correct	1921 ms	31724 KB	Output is correct
13	Correct	2898 ms	31980 KB	Output is correct
14	Correct	3378 ms	32208 KB	Output is correct
15	Correct	4785 ms	36660 KB	Output is correct
16	Correct	5220 ms	41832 KB	Output is correct
17	Correct	4792 ms	40556 KB	Output is correct