Submission #1033300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033300	2024-07-24T16:13:31 Z	s_tree	Regions (IOI09_regions)	C++17	26 / 100	6714 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 = 0;
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);
	int timer=0;
	vt<vt<int>> tinCol(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);
		}
	};
	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;
		}
	}

}

Subtask #1

11.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1 ms	344 KB	Time limit exceeded (wall clock)
2	Execution timed out	1 ms	344 KB	Time limit exceeded (wall clock)
3	Execution timed out	1 ms	344 KB	Time limit exceeded (wall clock)
4	Correct	2 ms	344 KB	Output is correct
5	Correct	4 ms	344 KB	Output is correct
6	Execution timed out	2 ms	916 KB	Time limit exceeded (wall clock)
7	Correct	10 ms	600 KB	Output is correct
8	Correct	14 ms	832 KB	Output is correct
9	Correct	27 ms	1848 KB	Output is correct
10	Correct	118 ms	2988 KB	Output is correct
11	Correct	133 ms	2320 KB	Output is correct
12	Correct	211 ms	4432 KB	Output is correct
13	Correct	220 ms	3408 KB	Output is correct
14	Correct	216 ms	3688 KB	Output is correct
15	Correct	177 ms	6252 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	754 ms	8428 KB	Output is correct
2	Correct	923 ms	7752 KB	Output is correct
3	Correct	1056 ms	10820 KB	Output is correct
4	Execution timed out	2136 ms	116340 KB	Time limit exceeded (wall clock)
5	Execution timed out	1136 ms	118608 KB	Time limit exceeded (wall clock)
6	Runtime error	2573 ms	131072 KB	Execution killed with signal 9
7	Runtime error	2834 ms	131072 KB	Execution killed with signal 9
8	Runtime error	1645 ms	131072 KB	Execution killed with signal 9
9	Runtime error	3832 ms	131072 KB	Execution killed with signal 9
10	Runtime error	1070 ms	131072 KB	Execution killed with signal 9
11	Runtime error	2619 ms	131072 KB	Execution killed with signal 9
12	Runtime error	6714 ms	131072 KB	Execution killed with signal 9
13	Runtime error	4049 ms	131072 KB	Execution killed with signal 9
14	Runtime error	4399 ms	131072 KB	Execution killed with signal 9
15	Runtime error	1710 ms	131072 KB	Execution killed with signal 9
16	Runtime error	1149 ms	131072 KB	Execution killed with signal 9
17	Runtime error	1477 ms	131072 KB	Execution killed with signal 9