oj.uz

Submission #1066286

# Submission time Handle Problem Language Result Execution time Memory
1066286 2024-08-19T17:23:14 Z Nonoze Regions (IOI09_regions) C++17
100 / 100
 3581 ms 28284 KB 
/*
*	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, calc2, 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);
}

int dfs2(int u, int i) {
	int comp=0;
	for (auto v: adj[u]) comp+=dfs2(v, i);
	if (a[u]==i) comp++;
	else calc2[i][a[u]]+=comp;
	return comp;
}

void dfs(int u) {
	in[u]=++m;
	if (cnt[a[u]]<SQRT) 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), calc2.resize(k);
	for (int i=0; i<k; i++) {
		if (cnt[i]>=SQRT) {
			calc[i].resize(k), calc2[i].resize(k);
			dfs(0, i, 0);
			dfs2(0, i);
		}
	}
	while (q--) {
		int u, v; read(u, v); u--, v--;
		if (cnt[u]>=SQRT) {
			cout << calc[u][v] << endl;
			continue;
		} else if (cnt[v]>=SQRT) {
			cout << calc2[v][u] << endl;
			continue;
		}
		int ans=0;
		for (auto x: nodes[u]) {
			auto it1=lower_bound(all(empls[v]), in[x]);
			auto it2=upper_bound(all(empls[v]), out[x]);
			ans+=it2-it1;
		}
		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 5 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 17 ms 600 KB Output is correct
9 Correct 24 ms 856 KB Output is correct
10 Correct 46 ms 1112 KB Output is correct
11 Correct 78 ms 1624 KB Output is correct
12 Correct 85 ms 2152 KB Output is correct
13 Correct 132 ms 2072 KB Output is correct
14 Correct 223 ms 2788 KB Output is correct
15 Correct 189 ms 4956 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1232 ms 6744 KB Output is correct
2 Correct 1389 ms 5724 KB Output is correct
3 Correct 1873 ms 8852 KB Output is correct
4 Correct 196 ms 3216 KB Output is correct
5 Correct 253 ms 4728 KB Output is correct
6 Correct 1128 ms 5208 KB Output is correct
7 Correct 1449 ms 7000 KB Output is correct
8 Correct 939 ms 11692 KB Output is correct
9 Correct 1868 ms 14620 KB Output is correct
10 Correct 3581 ms 19916 KB Output is correct
11 Correct 3502 ms 16876 KB Output is correct
12 Correct 1046 ms 17284 KB Output is correct
13 Correct 1512 ms 17476 KB Output is correct
14 Correct 2319 ms 17932 KB Output is correct
15 Correct 2541 ms 22840 KB Output is correct
16 Correct 2458 ms 28284 KB Output is correct
17 Correct 2571 ms 26644 KB Output is correct