oj.uz

답안 #1066293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066293 2024-08-19T17:26:36 Z Nonoze Regions (IOI09_regions) C++17
100 / 100
 3629 ms 27620 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, 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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