Submission #1033304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033304	2024-07-24T16:17:21 Z	s_tree	Regions (IOI09_regions)	C++17	80 / 100	5077 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 = 70;
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	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	13 ms	600 KB	Output is correct
8	Correct	17 ms	600 KB	Output is correct
9	Correct	18 ms	1112 KB	Output is correct
10	Correct	56 ms	1812 KB	Output is correct
11	Correct	74 ms	2460 KB	Output is correct
12	Correct	90 ms	3324 KB	Output is correct
13	Correct	159 ms	3824 KB	Output is correct
14	Correct	209 ms	4944 KB	Output is correct
15	Correct	177 ms	7732 KB	Output is correct

Subtask #2

65.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	723 ms	10916 KB	Output is correct
2	Correct	808 ms	10328 KB	Output is correct
3	Correct	1055 ms	13828 KB	Output is correct
4	Correct	238 ms	8020 KB	Output is correct
5	Correct	285 ms	10476 KB	Output is correct
6	Correct	493 ms	10980 KB	Output is correct
7	Correct	850 ms	19268 KB	Output is correct
8	Correct	1042 ms	48220 KB	Output is correct
9	Correct	3351 ms	92716 KB	Output is correct
10	Runtime error	988 ms	131072 KB	Execution killed with signal 9
11	Runtime error	2393 ms	131072 KB	Execution killed with signal 9
12	Correct	5077 ms	101884 KB	Output is correct
13	Correct	3551 ms	101876 KB	Output is correct
14	Correct	4131 ms	111264 KB	Output is correct
15	Runtime error	1491 ms	131072 KB	Execution killed with signal 9
16	Runtime error	1018 ms	131072 KB	Execution killed with signal 9
17	Correct	2242 ms	118104 KB	Output is correct