Submission #1033313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033313	2024-07-24T16:23:59 Z	s_tree	Regions (IOI09_regions)	C++17	100 / 100	3561 ms	36508 KB

regions

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T> bool chmin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool chmax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());


const int B = 1000;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n, r, q;
	cin >> n >> r >> q;
	vt<vt<int>> g(n+1);
	vt<vt<int>> col(r+1);
	vt<int> c(n+1);
	vt<vt<ll>> precomp(r+1);
	for(int i = 1;i<=n;i++) {
		if(i>1) {
			int par;
			cin >> par;
			g[par].pb(i);
		}
		int h;
		cin >> h;
		c[i] = h;
		col[h].pb(i);
	}
	vt<int> tin(n+1), tout(n+1);
	int timer=0;
	vt<vt<int>> tinCol(n+1);
	vt<vt<int>> toutCol(n+1);
	auto dfs = [&](int at,  auto &&dfs) -> void {
		tin[at]=++timer;	
		tinCol[c[at]].pb(tin[at]);
		for(int to:g[at]) {
			dfs(to, dfs);
		}
		tout[at]=++timer;
		toutCol[c[at]].pb(tout[at]);
	};
	int fixedCol=0;
	auto dfs2 = [&](int at,  auto &&dfs2) -> int {
		int cnt=0;
		for(int to:g[at]) {
			cnt+=dfs2(to, dfs2);
		}
		precomp[fixedCol][c[at]]+=cnt;
		cnt+=(fixedCol==c[at]);
		return cnt;
	};
	dfs(1, dfs);
	for(int i = 1;i<=r;i++) {
		if(sz(col[i])>B) {
			fixedCol=i;
			precomp[i].resize(r+1);
			dfs2(1, dfs2);
		}
	}
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		if(sz(col[r2])>B) {
			cout << precomp[r2][r1] << endl;
		}
		else {
			ll ans=0;
			for(int i:col[r2]) {
				ans+=lower_bound(all(tinCol[r1]), tin[i])-tinCol[r1].begin();
				ans-=lower_bound(all(toutCol[r1]), tin[i])-toutCol[r1].begin();
			}
			cout << ans << endl;
		}
	}

}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	2 ms	344 KB	Output is correct
5	Correct	5 ms	344 KB	Output is correct
6	Correct	9 ms	600 KB	Output is correct
7	Correct	14 ms	608 KB	Output is correct
8	Correct	14 ms	852 KB	Output is correct
9	Correct	24 ms	1112 KB	Output is correct
10	Correct	72 ms	1788 KB	Output is correct
11	Correct	82 ms	2460 KB	Output is correct
12	Correct	90 ms	3324 KB	Output is correct
13	Correct	129 ms	3360 KB	Output is correct
14	Correct	200 ms	4412 KB	Output is correct
15	Correct	189 ms	7268 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1599 ms	10624 KB	Output is correct
2	Correct	2117 ms	10072 KB	Output is correct
3	Correct	2262 ms	13336 KB	Output is correct
4	Correct	199 ms	4696 KB	Output is correct
5	Correct	241 ms	6556 KB	Output is correct
6	Correct	1111 ms	7696 KB	Output is correct
7	Correct	1358 ms	10384 KB	Output is correct
8	Correct	919 ms	16896 KB	Output is correct
9	Correct	1876 ms	22256 KB	Output is correct
10	Correct	3410 ms	28496 KB	Output is correct
11	Correct	3561 ms	26660 KB	Output is correct
12	Correct	1012 ms	26736 KB	Output is correct
13	Correct	1409 ms	26732 KB	Output is correct
14	Correct	1782 ms	29652 KB	Output is correct
15	Correct	2173 ms	32088 KB	Output is correct
16	Correct	1770 ms	35832 KB	Output is correct
17	Correct	2080 ms	36508 KB	Output is correct