oj.uz

Submission #883407

# Submission time Handle Problem Language Result Execution time Memory
883407 2023-12-05T09:07:06 Z serifefedartar Regions (IOI09_regions) C++17
100 / 100
 4125 ms 49512 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;
int tin[MAXN], tout[MAXN];
void dfs2(int node, int parent) {
	tin[node] = ++T;
	Rin[reg[node]].push_back(tin[node]);
	for (auto u : graph[node])
		dfs2(u, node);
	tout[node] = ++T;
	Rout[reg[node]].push_back(tout[node]);
}
 
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 (int i = 1; i <= R; i++) {
			sort(Rin[i].begin(), Rin[i].end());
			sort(Rout[i].begin(), Rout[i].end());
		}
 
		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 3 ms 9304 KB Output is correct
3 Correct 3 ms 9304 KB Output is correct
4 Correct 5 ms 9304 KB Output is correct
5 Correct 4 ms 9304 KB Output is correct
6 Correct 9 ms 9304 KB Output is correct
7 Correct 17 ms 9304 KB Output is correct
8 Correct 17 ms 9304 KB Output is correct
9 Correct 26 ms 9816 KB Output is correct
10 Correct 41 ms 9816 KB Output is correct
11 Correct 55 ms 10328 KB Output is correct
12 Correct 61 ms 10784 KB Output is correct
13 Correct 92 ms 10540 KB Output is correct
14 Correct 83 ms 10960 KB Output is correct
15 Correct 112 ms 14960 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 15004 KB Output is correct
2 Correct 524 ms 13644 KB Output is correct
3 Correct 747 ms 17752 KB Output is correct
4 Correct 172 ms 14000 KB Output is correct
5 Correct 247 ms 16044 KB Output is correct
6 Correct 358 ms 16376 KB Output is correct
7 Correct 532 ms 16288 KB Output is correct
8 Correct 753 ms 26236 KB Output is correct
9 Correct 1558 ms 31248 KB Output is correct
10 Correct 3358 ms 39364 KB Output is correct
11 Correct 4125 ms 36408 KB Output is correct
12 Correct 1262 ms 29712 KB Output is correct
13 Correct 1752 ms 31892 KB Output is correct
14 Correct 1853 ms 33588 KB Output is correct
15 Correct 2527 ms 42120 KB Output is correct
16 Correct 2264 ms 49512 KB Output is correct
17 Correct 2183 ms 47132 KB Output is correct