oj.uz

Submission #722471

# Submission time Handle Problem Language Result Execution time Memory
722471 2023-04-12T03:47:49 Z ono_de206 Regions (IOI09_regions) C++14
100 / 100
 4749 ms 31036 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
    return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
    return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
    return in;
}


template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 2e5 + 10, B = 400;
int cnt[610][25010], in[mxn], out[mxn], tt, kk[25010], s[mxn], h[mxn];
vector<int> g[mxn], p[25010], d[25010];

void dfs(int to) {
	in[to] = ++tt;
	d[h[to]].pb(in[to]);
	for(int x : g[to]) {
		dfs(x);
	}
	out[to] = tt;
}

void solve(int to, int cn, int id) {
	if (kk[id] > 600) exit(1);
	cnt[kk[id]][h[to]] += cn;
	cn += (h[to] == id);
	for(int x : g[to]) {
		solve(x, cn, id);
	}
	cn -= (h[to] == id);
}

void go() {
	int n, r, q;
	cin >> n >> r >> q;
	// scanf("%d %d %d", &n, &r, &q);
	for(int i = 1; i<= n; i++) {
		if(i == 1)
			// scanf("%d", &h[i]);
			cin >> h[i];
		else
			// scanf("%d %d", &s[i], &h[i]);
			cin >> s[i] >> h[i];
		p[h[i]].pb(i);
		if(i > 1) g[s[i]].pb(i);
	}
	dfs(1);
	tt = 0;
	for(int i = 1; i <= r; i++) {
		if(p[i].size() >= B) {
			kk[i] = ++tt;
			solve(1, 0, i);
		}
		sort(all(d[i]));
	}
	assert(tt <= 600);
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		// scanf("%d %d", &r1, &r2);
		if(p[r1].size() >= B) {
			cout << cnt[kk[r1]][r2] << '\n';
			// printf("%d\n", cnt[kk[r1]][r2]);
		}
		else {
			int ans = 0;
			for(int x : p[r1]) {
				int ll = lower_bound(all(d[r2]), in[x]) - d[r2].begin();
				int rr = upper_bound(all(d[r2]), out[x]) - d[r2].begin();
				ans += rr - ll;
			}
			cout << ans << '\n';
			// printf("%d\n", ans);
		}
		// fflush(stdout);
		cout.flush();
	}
}
 
signed main() {
	// #ifndef
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	// #endif
	// fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6096 KB Output is correct
2 Correct 4 ms 6080 KB Output is correct
3 Correct 5 ms 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 14 ms 6224 KB Output is correct
6 Correct 21 ms 6224 KB Output is correct
7 Correct 39 ms 6224 KB Output is correct
8 Correct 43 ms 6224 KB Output is correct
9 Correct 29 ms 6608 KB Output is correct
10 Correct 90 ms 6744 KB Output is correct
11 Correct 149 ms 6992 KB Output is correct
12 Correct 153 ms 7504 KB Output is correct
13 Correct 157 ms 7200 KB Output is correct
14 Correct 295 ms 7924 KB Output is correct
15 Correct 280 ms 9752 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 11212 KB Output is correct
2 Correct 2140 ms 10036 KB Output is correct
3 Correct 2682 ms 13016 KB Output is correct
4 Correct 334 ms 7892 KB Output is correct
5 Correct 376 ms 9164 KB Output is correct
6 Correct 562 ms 11208 KB Output is correct
7 Correct 1319 ms 11616 KB Output is correct
8 Correct 1158 ms 19840 KB Output is correct
9 Correct 2354 ms 15900 KB Output is correct
10 Correct 3349 ms 31036 KB Output is correct
11 Correct 4749 ms 16100 KB Output is correct
12 Correct 1797 ms 17616 KB Output is correct
13 Correct 2493 ms 17988 KB Output is correct
14 Correct 3357 ms 19552 KB Output is correct
15 Correct 4069 ms 22284 KB Output is correct
16 Correct 3615 ms 27500 KB Output is correct
17 Correct 3551 ms 28028 KB Output is correct