Submission #1033312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033312	2024-07-24T16:23:05 Z	s_tree	Regions (IOI09_regions)	C++17	90 / 100	2953 ms	131072 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 = 200;
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	1 ms	344 KB	Output is correct
2	Correct	1 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	4 ms	344 KB	Output is correct
6	Correct	9 ms	596 KB	Output is correct
7	Correct	24 ms	600 KB	Output is correct
8	Correct	25 ms	600 KB	Output is correct
9	Correct	26 ms	1112 KB	Output is correct
10	Correct	52 ms	1624 KB	Output is correct
11	Correct	101 ms	2460 KB	Output is correct
12	Correct	96 ms	3320 KB	Output is correct
13	Correct	144 ms	3364 KB	Output is correct
14	Correct	221 ms	4412 KB	Output is correct
15	Correct	195 ms	7280 KB	Output is correct

Subtask #2

75.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1144 ms	10760 KB	Output is correct
2	Correct	902 ms	10336 KB	Output is correct
3	Correct	2368 ms	13332 KB	Output is correct
4	Correct	185 ms	4708 KB	Output is correct
5	Correct	237 ms	6560 KB	Output is correct
6	Correct	485 ms	10976 KB	Output is correct
7	Correct	1047 ms	14296 KB	Output is correct
8	Correct	830 ms	24736 KB	Output is correct
9	Correct	1711 ms	34000 KB	Output is correct
10	Correct	2183 ms	98020 KB	Output is correct
11	Runtime error	2406 ms	131072 KB	Execution killed with signal 9
12	Correct	2953 ms	62808 KB	Output is correct
13	Correct	2461 ms	63556 KB	Output is correct
14	Correct	1840 ms	31088 KB	Output is correct
15	Correct	2343 ms	32088 KB	Output is correct
16	Runtime error	1100 ms	131072 KB	Execution killed with signal 9
17	Correct	2230 ms	37956 KB	Output is correct