Submission #1033307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033307	2024-07-24T16:19:45 Z	s_tree	Regions (IOI09_regions)	C++17	100 / 100	3579 ms	37940 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 = 500;
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	3 ms	344 KB	Output is correct
5	Correct	5 ms	344 KB	Output is correct
6	Correct	12 ms	600 KB	Output is correct
7	Correct	10 ms	600 KB	Output is correct
8	Correct	17 ms	600 KB	Output is correct
9	Correct	25 ms	1112 KB	Output is correct
10	Correct	48 ms	1792 KB	Output is correct
11	Correct	86 ms	2476 KB	Output is correct
12	Correct	96 ms	3316 KB	Output is correct
13	Correct	122 ms	3408 KB	Output is correct
14	Correct	205 ms	4412 KB	Output is correct
15	Correct	190 ms	7504 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1483 ms	10832 KB	Output is correct
2	Correct	1939 ms	10088 KB	Output is correct
3	Correct	2188 ms	13336 KB	Output is correct
4	Correct	191 ms	4944 KB	Output is correct
5	Correct	268 ms	6560 KB	Output is correct
6	Correct	1146 ms	7696 KB	Output is correct
7	Correct	1413 ms	10384 KB	Output is correct
8	Correct	1014 ms	16896 KB	Output is correct
9	Correct	1938 ms	22256 KB	Output is correct
10	Correct	3373 ms	28496 KB	Output is correct
11	Correct	3579 ms	26668 KB	Output is correct
12	Correct	1105 ms	26736 KB	Output is correct
13	Correct	1598 ms	26724 KB	Output is correct
14	Correct	1868 ms	31096 KB	Output is correct
15	Correct	2483 ms	32084 KB	Output is correct
16	Correct	2069 ms	35832 KB	Output is correct
17	Correct	2290 ms	37940 KB	Output is correct