oj.uz

Submission #366641

# Submission time Handle Problem Language Result Execution time Memory
366641 2021-02-14T20:09:39 Z penguinhacker Regions (IOI09_regions) C++14
100 / 100
 5258 ms 70252 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 = 250; // 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 19308 KB Output is correct
2 Correct 13 ms 19180 KB Output is correct
3 Correct 17 ms 19180 KB Output is correct
4 Correct 19 ms 19180 KB Output is correct
5 Correct 22 ms 19180 KB Output is correct
6 Correct 31 ms 19180 KB Output is correct
7 Correct 42 ms 19308 KB Output is correct
8 Correct 44 ms 19308 KB Output is correct
9 Correct 57 ms 19692 KB Output is correct
10 Correct 88 ms 19820 KB Output is correct
11 Correct 183 ms 20076 KB Output is correct
12 Correct 142 ms 20588 KB Output is correct
13 Correct 272 ms 20460 KB Output is correct
14 Correct 343 ms 21100 KB Output is correct
15 Correct 308 ms 23148 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2063 ms 24508 KB Output is correct
2 Correct 1805 ms 23644 KB Output is correct
3 Correct 3599 ms 26220 KB Output is correct
4 Correct 342 ms 21100 KB Output is correct
5 Correct 384 ms 22392 KB Output is correct
6 Correct 434 ms 24300 KB Output is correct
7 Correct 1451 ms 25904 KB Output is correct
8 Correct 1085 ms 32236 KB Output is correct
9 Correct 2223 ms 35948 KB Output is correct
10 Correct 3385 ms 43992 KB Output is correct
11 Correct 5258 ms 70252 KB Output is correct
12 Correct 2019 ms 32184 KB Output is correct
13 Correct 2779 ms 32108 KB Output is correct
14 Correct 2657 ms 33900 KB Output is correct
15 Correct 4051 ms 35648 KB Output is correct
16 Correct 4143 ms 39172 KB Output is correct
17 Correct 3371 ms 39972 KB Output is correct