oj.uz

Submission #366642

# Submission time Handle Problem Language Result Execution time Memory
366642 2021-02-14T20:12:38 Z penguinhacker Regions (IOI09_regions) C++14
100 / 100
 6207 ms 43992 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 = 350; // 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 15 ms 19180 KB Output is correct
3 Correct 16 ms 19180 KB Output is correct
4 Correct 17 ms 19180 KB Output is correct
5 Correct 23 ms 19180 KB Output is correct
6 Correct 30 ms 19180 KB Output is correct
7 Correct 51 ms 19308 KB Output is correct
8 Correct 56 ms 19308 KB Output is correct
9 Correct 54 ms 19820 KB Output is correct
10 Correct 67 ms 19772 KB Output is correct
11 Correct 156 ms 20204 KB Output is correct
12 Correct 202 ms 20588 KB Output is correct
13 Correct 242 ms 20460 KB Output is correct
14 Correct 401 ms 21076 KB Output is correct
15 Correct 390 ms 23048 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2161 ms 24608 KB Output is correct
2 Correct 2480 ms 23660 KB Output is correct
3 Correct 3904 ms 26168 KB Output is correct
4 Correct 384 ms 21100 KB Output is correct
5 Correct 444 ms 22392 KB Output is correct
6 Correct 608 ms 24428 KB Output is correct
7 Correct 1607 ms 25324 KB Output is correct
8 Correct 1263 ms 32196 KB Output is correct
9 Correct 2569 ms 29420 KB Output is correct
10 Correct 3654 ms 43992 KB Output is correct
11 Correct 6207 ms 30092 KB Output is correct
12 Correct 2031 ms 32148 KB Output is correct
13 Correct 2592 ms 32140 KB Output is correct
14 Correct 3127 ms 33872 KB Output is correct
15 Correct 4154 ms 35660 KB Output is correct
16 Correct 4014 ms 39180 KB Output is correct
17 Correct 4124 ms 39924 KB Output is correct