oj.uz

Submission #883406

# Submission time Handle Problem Language Result Execution time Memory
883406 2023-12-05T09:04:47 Z serifefedartar Regions (IOI09_regions) C++17
100 / 100
 3721 ms 53268 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 2e5 +  100;

vector<vector<int>> graph;
int reg[MAXN], dp[505][505];
vector<int> cnt[MAXN], Rin[25100], Rout[25100], plc[25100];
map<pair<int,int>, pair<int,bool>> memo;

void dfs(int node, int parent) {
	cnt[node][reg[node]]++;
	for (int reg_other = 1; reg_other <= 500; reg_other++)
		dp[reg_other][reg[node]] += cnt[node][reg_other];
	for (auto u : graph[node]) {
		swap(cnt[u], cnt[node]);
		dfs(u, node);
	}
	cnt[node][reg[node]]--;
	swap(cnt[parent], cnt[node]);
}
	
int T = 0;
vector<pair<int,int>> v;
int tin[MAXN], tout[MAXN];
void dfs2(int node, int parent) {
	tin[node] = ++T;
	v.push_back({node, 1});
	for (auto u : graph[node])
		dfs2(u, node);
	tout[node] = ++T;
	v.push_back({node, 0});
}

int main() {
	fast
	int N, R, Q, a, b;
	cin >> N >> R >> Q;

	graph = vector<vector<int>>(N+1, vector<int>());
	cin >> reg[1];
	plc[reg[1]].push_back(1);
	for (int i = 2; i <= N; i++) {
		int S;
		cin >> S >> reg[i];
		plc[reg[i]].push_back(i);
		graph[S].push_back(i);
	}

	if (R <= 500) {
		cnt[1] = vector<int>(505, 0);
		dfs(1, 1);
		for (int i = 0; i < Q; i++) {
			cin >> a >> b;
			cout << dp[a][b] << endl;
		}
	} else {
		dfs2(1, 1);
		for (auto u : v) {
			if (u.s == 1)
				Rin[reg[u.f]].push_back(tin[u.f]);
			else
				Rout[reg[u.f]].push_back(tout[u.f]);
		}

		for (int i = 0; i < Q; i++) {
			cin >> a >> b;
			if (memo[{a, b}].s == false) {
				int ans = 0;
				if (plc[a].size() < plc[b].size())
					for (auto u : plc[a])
						ans += (upper_bound(Rin[b].begin(), Rin[b].end(), tout[u]) - Rin[b].begin()) - (upper_bound(Rin[b].begin(), Rin[b].end(), tin[u]) - Rin[b].begin());
				else
					for (auto u : plc[b])
						ans += (upper_bound(Rin[a].begin(), Rin[a].end(), tin[u]) - Rin[a].begin()) - (upper_bound(Rout[a].begin(), Rout[a].end(), tin[u]) - Rout[a].begin());
				memo[{a, b}] = {ans, 1};
			}
			cout << memo[{a, b}].f << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9556 KB Output is correct
4 Correct 3 ms 9304 KB Output is correct
5 Correct 4 ms 9304 KB Output is correct
6 Correct 13 ms 9304 KB Output is correct
7 Correct 16 ms 9304 KB Output is correct
8 Correct 16 ms 9304 KB Output is correct
9 Correct 27 ms 9816 KB Output is correct
10 Correct 51 ms 9816 KB Output is correct
11 Correct 55 ms 10328 KB Output is correct
12 Correct 80 ms 10792 KB Output is correct
13 Correct 77 ms 10496 KB Output is correct
14 Correct 78 ms 11188 KB Output is correct
15 Correct 109 ms 15012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 14972 KB Output is correct
2 Correct 554 ms 13572 KB Output is correct
3 Correct 776 ms 17752 KB Output is correct
4 Correct 183 ms 14264 KB Output is correct
5 Correct 250 ms 16704 KB Output is correct
6 Correct 381 ms 16720 KB Output is correct
7 Correct 552 ms 17804 KB Output is correct
8 Correct 711 ms 27900 KB Output is correct
9 Correct 1447 ms 33644 KB Output is correct
10 Correct 2976 ms 42276 KB Output is correct
11 Correct 3721 ms 38556 KB Output is correct
12 Correct 1117 ms 33432 KB Output is correct
13 Correct 1575 ms 35816 KB Output is correct
14 Correct 1777 ms 37272 KB Output is correct
15 Correct 2497 ms 45572 KB Output is correct
16 Correct 2159 ms 53268 KB Output is correct
17 Correct 2176 ms 51424 KB Output is correct