oj.uz

Submission #700887

# Submission time Handle Problem Language Result Execution time Memory
700887 2023-02-19T10:29:01 Z badont Regions (IOI09_regions) C++17
100 / 100
 3858 ms 58760 KB 
#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

template<typename T>
struct fen {
	vector<T> tr;
	ll mxn;

	fen(ll sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(ll g, T k) {
		g++;
		assert(g != 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(ll g) {
		g++;
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(ll l, ll r) { return ge(r) - ge(l - 1); }

	//maxi and mini only work with positive numbers
	ll maxi(T k) {
		//max i such that ge(i) <= k.
		//log(n) vs log^2(n) binary search
		T running = 0; ll res = 0;
		ll lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] > k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res;
	}

	ll mini(T k) {
		//kth order statistic
		T running = 0; ll res = 0;
		ll lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] >= k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res + 1;
	}
};

//var 
ll T;

void solve() {
	int n, r, q;
	cin >> n >> r >> q;

	vector<int> region(n), parent(n);
	F0R (i, n) {
		if (i) cin >> parent[i];
		parent[i]--;
		cin >> region[i];
		region[i]--;
	}

	vector adj(n, vector<int>());
	FOR (i, n - 1) {
		adj[parent[i]].pb(i);
	}
	vector<int> tin(n), tout(n);

	int cc = 0;
	auto dfs = [&](auto dfs, int g, int p) -> void {
		tin[g] = cc++;
		for (auto u : adj[g]) if (u != p) {
			dfs(dfs, u, g);
		}
		tout[g] = cc++;
	};

	dfs(dfs, 0, -1);
	

	vector in_region(r, vector<int>());
	F0R (i, n) in_region[region[i]].pb(i);
	region.clear();

	constexpr int B = 250;
	// at most n / B greater than B

	vector<short> GB;
	F0R (i, r) if ((int)in_region[i].size() > B) {
		GB.pb(i);
	}
	
	//debug(tin, tout);

	sort(all(GB));
	auto big_region = [&](short x) -> int {
		auto iter = lower_bound(all(GB), x);
		if (iter == GB.end() or *iter != x) return -1;
		return iter - GB.begin();
	};

	//debug(in_region);
	vector region_locs(r, vector<int>());
	F0R (i, r) {
		for (auto node : in_region[i]) {
			region_locs[i].pb(tin[node]);
		}
		sort(all(region_locs[i]));
	}

	int M = (int)GB.size();
	vector dp(M, vector<int>(r));

	fen<int> tree(cc);
	F0R (i1, M) {
		int r1 = GB[i1];
		vector<int> pf(cc);

		for (auto node : in_region[r1]) {
			pf[tin[node]]++;
			pf[tout[node]]--;
		} 

		FOR (i, cc - 1) pf[i] += pf[i - 1];
		F0R (r2, r) {
			for (auto node : in_region[r2]) {
				dp[i1][r2] += pf[tin[node]];
			}
		}
	}

	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;

		int get_1 = big_region(r1);
		if (get_1 == -1) {
			ll ans = 0;

			for (auto node : in_region[r1]) {
				auto iter_r = upper_bound(all(region_locs[r2]), tout[node]);
				auto iter_l = lower_bound(all(region_locs[r2]), tin[node]);
				ans += iter_r - iter_l;
			}
			cout << ans << endl;
		} else {
			cout << dp[get_1][r2] << endl;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 15 ms 336 KB Output is correct
7 Correct 31 ms 336 KB Output is correct
8 Correct 33 ms 464 KB Output is correct
9 Correct 44 ms 1000 KB Output is correct
10 Correct 75 ms 1104 KB Output is correct
11 Correct 116 ms 1708 KB Output is correct
12 Correct 150 ms 2360 KB Output is correct
13 Correct 205 ms 2176 KB Output is correct
14 Correct 310 ms 2984 KB Output is correct
15 Correct 255 ms 5820 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1641 ms 8192 KB Output is correct
2 Correct 1282 ms 7304 KB Output is correct
3 Correct 2651 ms 10560 KB Output is correct
4 Correct 238 ms 3248 KB Output is correct
5 Correct 263 ms 5108 KB Output is correct
6 Correct 521 ms 7448 KB Output is correct
7 Correct 1193 ms 9720 KB Output is correct
8 Correct 1026 ms 17876 KB Output is correct
9 Correct 1589 ms 22764 KB Output is correct
10 Correct 2859 ms 33020 KB Output is correct
11 Correct 3858 ms 58760 KB Output is correct
12 Correct 1501 ms 20036 KB Output is correct
13 Correct 2200 ms 20208 KB Output is correct
14 Correct 2292 ms 22284 KB Output is correct
15 Correct 3269 ms 25220 KB Output is correct
16 Correct 2782 ms 30436 KB Output is correct
17 Correct 2574 ms 30616 KB Output is correct