oj.uz

Submission #700885

# Submission time Handle Problem Language Result Execution time Memory
700885 2023-02-19T10:20:23 Z badont Regions (IOI09_regions) C++17
40 / 100
 8000 ms 57160 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 (x, r) {
		for (auto node : in_region[x]) {
			tree.upd(tin[node], 1);
		}

		F0R (i1, M) {
			int r1 = GB[i1];
			for (auto node : in_region[r1])
				dp[i1][x] += tree.rng(tin[node], tout[node]);
		}

		for (auto node : in_region[x]) {
			tree.upd(tin[node], -1);
		}
	}

	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 2 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Correct 30 ms 336 KB Output is correct
8 Correct 34 ms 464 KB Output is correct
9 Correct 45 ms 1024 KB Output is correct
10 Correct 79 ms 1104 KB Output is correct
11 Correct 122 ms 1684 KB Output is correct
12 Correct 138 ms 2360 KB Output is correct
13 Correct 155 ms 2176 KB Output is correct
14 Correct 274 ms 2992 KB Output is correct
15 Correct 233 ms 5840 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2051 ms 7604 KB Output is correct
2 Correct 1909 ms 6672 KB Output is correct
3 Correct 3051 ms 9852 KB Output is correct
4 Correct 229 ms 3244 KB Output is correct
5 Correct 354 ms 5112 KB Output is correct
6 Execution timed out 8025 ms 7036 KB Time limit exceeded
7 Execution timed out 8007 ms 9168 KB Time limit exceeded
8 Execution timed out 8087 ms 17056 KB Time limit exceeded
9 Execution timed out 8007 ms 21584 KB Time limit exceeded
10 Execution timed out 8039 ms 31612 KB Time limit exceeded
11 Execution timed out 8013 ms 57160 KB Time limit exceeded
12 Execution timed out 8057 ms 18432 KB Time limit exceeded
13 Execution timed out 8083 ms 18692 KB Time limit exceeded
14 Execution timed out 8023 ms 20664 KB Time limit exceeded
15 Execution timed out 8105 ms 23652 KB Time limit exceeded
16 Execution timed out 8096 ms 28816 KB Time limit exceeded
17 Execution timed out 8100 ms 29028 KB Time limit exceeded