Submission #1033305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033305	2024-07-24T16:18:14 Z	s_tree	Regions (IOI09_regions)	C++17	80 / 100	5324 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 = 100;
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	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	4 ms	344 KB	Output is correct
6	Correct	8 ms	600 KB	Output is correct
7	Correct	10 ms	600 KB	Output is correct
8	Correct	15 ms	600 KB	Output is correct
9	Correct	19 ms	1112 KB	Output is correct
10	Correct	45 ms	1784 KB	Output is correct
11	Correct	76 ms	2452 KB	Output is correct
12	Correct	80 ms	3160 KB	Output is correct
13	Correct	117 ms	3356 KB	Output is correct
14	Correct	188 ms	4732 KB	Output is correct
15	Correct	167 ms	7504 KB	Output is correct

Subtask #2

65.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	701 ms	10916 KB	Output is correct
2	Correct	796 ms	10332 KB	Output is correct
3	Correct	965 ms	13824 KB	Output is correct
4	Correct	209 ms	7832 KB	Output is correct
5	Correct	260 ms	8360 KB	Output is correct
6	Correct	451 ms	11088 KB	Output is correct
7	Correct	780 ms	18064 KB	Output is correct
8	Correct	888 ms	35852 KB	Output is correct
9	Correct	2995 ms	92708 KB	Output is correct
10	Runtime error	910 ms	131072 KB	Execution killed with signal 9
11	Runtime error	2258 ms	131072 KB	Execution killed with signal 9
12	Correct	5324 ms	101888 KB	Output is correct
13	Correct	3701 ms	101880 KB	Output is correct
14	Correct	4124 ms	111252 KB	Output is correct
15	Runtime error	1504 ms	131072 KB	Execution killed with signal 9
16	Runtime error	989 ms	131072 KB	Execution killed with signal 9
17	Correct	2230 ms	118108 KB	Output is correct