Submission #1066293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1066293	2024-08-19T17:26:36 Z	Nonoze	Regions (IOI09_regions)	C++17	100 / 100	3629 ms	27620 KB

regions

/*
*	Author: Nonoze
*	Created: Monday 19/08/2024
*/
#include <bits/stdc++.h>
using namespace std;

#ifndef _IN_LOCAL
	#define dbg(...)
#endif

// #define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);}
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}

int n, k, m=-1, q, SQRT;
vector<int> a, in, out, cnt;
vector<vector<int>> adj, calc, empls;
string s;

void dfs(int u, int i, int comp) {
	if (a[u]==i) comp++;
	else calc[i][a[u]]+=comp;
	for (auto v: adj[u]) dfs(v, i, comp);
}

void dfs(int u) {
	in[u]=++m;
	empls[a[u]].pb(m);
	for (auto v: adj[u]) dfs(v);
	out[u]=m;
}

void solve() {
	read(n, k, q); SQRT=sqrt(n)*5;
	a.resize(n), adj.resize(n), in.resize(n), out.resize(n), cnt.resize(k, 0), empls.resize(k);
	vector<vector<int>> nodes(k);
	for (int i=0; i<n; i++) {
		if (i) {
			int x; read(x); x--;
			adj[x].pb(i);
		}
		read(a[i]); a[i]--; cnt[a[i]]++;
		nodes[a[i]].pb(i);
	}
	dfs(0);
	calc.resize(k);
	for (int i=0; i<k; i++) {
		if (cnt[i]>=SQRT) {
			calc[i].resize(k);
			dfs(0, i, 0);
		}
	}
	while (q--) {
		int u, v; read(u, v); u--, v--;
		if (cnt[u]>=SQRT) {
			cout << calc[u][v] << endl;
			continue;
		}
		int ans=0;
		for (auto x: nodes[u]) {
			ans += upper_bound(all(empls[v]), out[x]) - lower_bound(all(empls[v]), in[x]);
		}
		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	2 ms	344 KB	Output is correct
5	Correct	6 ms	344 KB	Output is correct
6	Correct	10 ms	344 KB	Output is correct
7	Correct	17 ms	344 KB	Output is correct
8	Correct	19 ms	600 KB	Output is correct
9	Correct	23 ms	856 KB	Output is correct
10	Correct	48 ms	1112 KB	Output is correct
11	Correct	103 ms	1624 KB	Output is correct
12	Correct	101 ms	2136 KB	Output is correct
13	Correct	144 ms	2060 KB	Output is correct
14	Correct	209 ms	2784 KB	Output is correct
15	Correct	202 ms	4952 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1529 ms	6868 KB	Output is correct
2	Correct	2073 ms	5836 KB	Output is correct
3	Correct	2269 ms	9048 KB	Output is correct
4	Correct	182 ms	3124 KB	Output is correct
5	Correct	250 ms	4600 KB	Output is correct
6	Correct	1105 ms	5044 KB	Output is correct
7	Correct	1397 ms	6752 KB	Output is correct
8	Correct	1048 ms	11448 KB	Output is correct
9	Correct	1872 ms	14264 KB	Output is correct
10	Correct	3629 ms	19336 KB	Output is correct
11	Correct	3399 ms	16288 KB	Output is correct
12	Correct	1156 ms	16904 KB	Output is correct
13	Correct	1593 ms	17104 KB	Output is correct
14	Correct	2379 ms	17536 KB	Output is correct
15	Correct	2676 ms	22224 KB	Output is correct
16	Correct	2480 ms	27620 KB	Output is correct
17	Correct	2578 ms	26096 KB	Output is correct