oj.uz

Submission #366879

# Submission time Handle Problem Language Result Execution time Memory
366879 2021-02-15T15:44:52 Z kostia244 Regions (IOI09_regions) C++17
50 / 100
 5880 ms 41836 KB 
#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]];
		}
		//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 15 ms 19948 KB Output is correct
4 Correct 16 ms 19948 KB Output is correct
5 Correct 22 ms 19948 KB Output is correct
6 Correct 40 ms 20204 KB Output is correct
7 Correct 40 ms 20076 KB Output is correct
8 Correct 61 ms 20076 KB Output is correct
9 Correct 65 ms 20460 KB Output is correct
10 Correct 122 ms 20588 KB Output is correct
11 Correct 153 ms 20844 KB Output is correct
12 Correct 116 ms 21356 KB Output is correct
13 Correct 234 ms 21100 KB Output is correct
14 Correct 384 ms 21740 KB Output is correct
15 Correct 492 ms 24272 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 25196 KB Execution killed with signal 13
2 Runtime error 48 ms 23916 KB Execution killed with signal 13
3 Runtime error 46 ms 26732 KB Execution killed with signal 13
4 Correct 292 ms 21868 KB Output is correct
5 Correct 384 ms 23404 KB Output is correct
6 Incorrect 1765 ms 23404 KB Output isn't correct
7 Incorrect 1662 ms 24684 KB Output isn't correct
8 Correct 1349 ms 30212 KB Output is correct
9 Correct 2526 ms 30828 KB Output is correct
10 Runtime error 95 ms 36460 KB Execution killed with signal 13
11 Incorrect 5880 ms 31212 KB Output isn't correct
12 Correct 1991 ms 31724 KB Output is correct
13 Correct 2747 ms 31944 KB Output is correct
14 Runtime error 164 ms 32160 KB Execution killed with signal 13
15 Runtime error 753 ms 36716 KB Execution killed with signal 13
16 Correct 5487 ms 41836 KB Output is correct
17 Runtime error 112 ms 40556 KB Execution killed with signal 13