Submission #1033311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033311	2024-07-24T16:22:53 Z	s_tree	Regions (IOI09_regions)	C++17	100 / 100	4048 ms	48132 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 = 300;
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	2 ms	344 KB	Output is correct
4	Correct	2 ms	344 KB	Output is correct
5	Correct	4 ms	344 KB	Output is correct
6	Correct	9 ms	600 KB	Output is correct
7	Correct	10 ms	600 KB	Output is correct
8	Correct	19 ms	600 KB	Output is correct
9	Correct	25 ms	1112 KB	Output is correct
10	Correct	42 ms	1872 KB	Output is correct
11	Correct	64 ms	2392 KB	Output is correct
12	Correct	92 ms	3408 KB	Output is correct
13	Correct	121 ms	3364 KB	Output is correct
14	Correct	184 ms	4412 KB	Output is correct
15	Correct	147 ms	7268 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1355 ms	10636 KB	Output is correct
2	Correct	1980 ms	10072 KB	Output is correct
3	Correct	2273 ms	13332 KB	Output is correct
4	Correct	178 ms	4704 KB	Output is correct
5	Correct	223 ms	6560 KB	Output is correct
6	Correct	429 ms	10976 KB	Output is correct
7	Correct	963 ms	14228 KB	Output is correct
8	Correct	928 ms	24732 KB	Output is correct
9	Correct	1980 ms	27888 KB	Output is correct
10	Correct	2334 ms	48132 KB	Output is correct
11	Correct	4048 ms	45524 KB	Output is correct
12	Correct	1109 ms	26728 KB	Output is correct
13	Correct	1543 ms	26724 KB	Output is correct
14	Correct	1787 ms	31104 KB	Output is correct
15	Correct	2336 ms	32084 KB	Output is correct
16	Correct	1977 ms	35836 KB	Output is correct
17	Correct	2210 ms	37944 KB	Output is correct