oj.uz

Submission #366880

# Submission time Handle Problem Language Result Execution time Memory
366880 2021-02-15T15:49:58 Z kostia244 Regions (IOI09_regions) C++17
60 / 100
 4512 ms 50668 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn = 2e5 + 5, C = 400;
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;
		assert(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 15 ms 19948 KB Output is correct
2 Correct 15 ms 19948 KB Output is correct
3 Correct 16 ms 19948 KB Output is correct
4 Correct 21 ms 19948 KB Output is correct
5 Correct 21 ms 19948 KB Output is correct
6 Correct 32 ms 20076 KB Output is correct
7 Correct 42 ms 20076 KB Output is correct
8 Correct 53 ms 20076 KB Output is correct
9 Correct 64 ms 20716 KB Output is correct
10 Correct 70 ms 20588 KB Output is correct
11 Correct 137 ms 20844 KB Output is correct
12 Correct 143 ms 21612 KB Output is correct
13 Correct 200 ms 21100 KB Output is correct
14 Correct 282 ms 21740 KB Output is correct
15 Correct 383 ms 26092 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 25836 KB Execution killed with signal 13
2 Runtime error 50 ms 23916 KB Execution killed with signal 13
3 Runtime error 56 ms 28568 KB Execution killed with signal 13
4 Correct 228 ms 22124 KB Output is correct
5 Correct 413 ms 24684 KB Output is correct
6 Incorrect 1255 ms 23764 KB Output isn't correct
7 Correct 1386 ms 24684 KB Output is correct
8 Correct 1225 ms 33260 KB Output is correct
9 Correct 2073 ms 31596 KB Output is correct
10 Runtime error 103 ms 40428 KB Execution killed with signal 13
11 Correct 4512 ms 30956 KB Output is correct
12 Correct 1905 ms 31976 KB Output is correct
13 Correct 2435 ms 32876 KB Output is correct
14 Runtime error 156 ms 32492 KB Execution killed with signal 13
15 Runtime error 631 ms 39916 KB Execution killed with signal 13
16 Correct 4080 ms 50668 KB Output is correct
17 Runtime error 123 ms 48364 KB Execution killed with signal 13