oj.uz

Submission #1066279

# Submission time Handle Problem Language Result Execution time Memory
1066279 2024-08-19T17:19:56 Z Nonoze Regions (IOI09_regions) C++17
100 / 100
 3356 ms 40680 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);
	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 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 19 ms 600 KB Output is correct
9 Correct 26 ms 856 KB Output is correct
10 Correct 50 ms 1112 KB Output is correct
11 Correct 70 ms 1624 KB Output is correct
12 Correct 82 ms 2136 KB Output is correct
13 Correct 119 ms 2068 KB Output is correct
14 Correct 199 ms 2796 KB Output is correct
15 Correct 205 ms 5584 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 6680 KB Output is correct
2 Correct 1079 ms 5660 KB Output is correct
3 Correct 1908 ms 8860 KB Output is correct
4 Correct 202 ms 3216 KB Output is correct
5 Correct 262 ms 4708 KB Output is correct
6 Correct 529 ms 8452 KB Output is correct
7 Correct 815 ms 10880 KB Output is correct
8 Correct 857 ms 20376 KB Output is correct
9 Correct 1861 ms 14620 KB Output is correct
10 Correct 1969 ms 40680 KB Output is correct
11 Correct 3356 ms 16880 KB Output is correct
12 Correct 1045 ms 17280 KB Output is correct
13 Correct 1458 ms 17476 KB Output is correct
14 Correct 1709 ms 20928 KB Output is correct
15 Correct 2605 ms 22840 KB Output is correct
16 Correct 2499 ms 28280 KB Output is correct
17 Correct 2214 ms 29636 KB Output is correct