oj.uz

Submission #366643

# Submission time Handle Problem Language Result Execution time Memory
366643 2021-02-14T20:13:02 Z penguinhacker Regions (IOI09_regions) C++14
100 / 100
 4230 ms 89700 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"

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

const int mxN = 200000;
const int B = 200; // change this
int n, m, q, reg[mxN], p[mxN], tin[mxN], tout[mxN], timer = 0, dp[mxN + 1], r[mxN];
vector<int> adj[mxN], oc[mxN], pos[mxN];
vector<int> pre[mxN];

void dfs(int u = 0) {
	tin[u] = timer++;
	pos[reg[u]].push_back(tin[u]);
	for (int v : adj[u]) dfs(v);
	tout[u] = timer - 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < n; ++i) {
		if (i > 0) {
			cin >> p[i], --p[i];
			adj[p[i]].push_back(i);
		}
		cin >> reg[i], --reg[i];
	}
	dfs();
	for (int i = 0; i < n; ++i) {
		r[tin[i]] = i;
		oc[reg[i]].push_back(i);
	}
	for (int i = 0; i < m; ++i) if (oc[i].size() > B) {
		pre[i].resize(m);
		for (int u : oc[i]) {
			++dp[tin[u]];
			--dp[tout[u] + 1];
		}
		for (int j = 1; j < n; ++j) dp[j] += dp[j - 1];
		for (int j = 0; j < n; ++j) pre[i][reg[r[j]]] += dp[j];
		pre[i][i] -= oc[i].size();
		//debug(pre[i]);
		memset(dp, 0, 4 * n);
	}
	for (int i = 0; i < q; ++i) {
		int a, b; cin >> a >> b, --a, --b;
		if (oc[a].size() > B) {
			cout << pre[a][b] << endl;
			continue;
		}
		int ans = 0;
		for (int u : oc[a]) {
			ans += upper_bound(pos[b].begin(), pos[b].end(), tout[u]) - lower_bound(pos[b].begin(), pos[b].end(), tin[u]);
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19180 KB Output is correct
2 Correct 13 ms 19180 KB Output is correct
3 Correct 15 ms 19180 KB Output is correct
4 Correct 16 ms 19180 KB Output is correct
5 Correct 23 ms 19312 KB Output is correct
6 Correct 33 ms 19180 KB Output is correct
7 Correct 37 ms 19308 KB Output is correct
8 Correct 43 ms 19308 KB Output is correct
9 Correct 79 ms 19692 KB Output is correct
10 Correct 137 ms 19948 KB Output is correct
11 Correct 183 ms 20164 KB Output is correct
12 Correct 180 ms 20588 KB Output is correct
13 Correct 260 ms 20332 KB Output is correct
14 Correct 393 ms 20972 KB Output is correct
15 Correct 366 ms 23148 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1657 ms 24428 KB Output is correct
2 Correct 1050 ms 23748 KB Output is correct
3 Correct 3932 ms 26168 KB Output is correct
4 Correct 308 ms 21100 KB Output is correct
5 Correct 437 ms 22392 KB Output is correct
6 Correct 474 ms 24336 KB Output is correct
7 Correct 1466 ms 25904 KB Output is correct
8 Correct 1301 ms 32196 KB Output is correct
9 Correct 2550 ms 36052 KB Output is correct
10 Correct 3278 ms 68848 KB Output is correct
11 Correct 3320 ms 89700 KB Output is correct
12 Correct 2300 ms 50284 KB Output is correct
13 Correct 2524 ms 50528 KB Output is correct
14 Correct 3429 ms 33900 KB Output is correct
15 Correct 4230 ms 35648 KB Output is correct
16 Correct 2758 ms 88248 KB Output is correct
17 Correct 4016 ms 39924 KB Output is correct