oj.uz

Submission #883367

# Submission time Handle Problem Language Result Execution time Memory
883367 2023-12-05T08:20:23 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3797 ms 52780 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(tin[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 = 0; i < Q; i++) {
			cin >> a >> b;
			if (memo[{a, b}].s == false) {
				int ans = 0;
				if (Rin[a].size() < Rin[b].size())
					for (auto u : plc[a])
						ans += (upper_bound(Rin[b].begin(), Rin[b].end(), tout[u]) - Rin[b].begin()) - (lower_bound(Rin[b].begin(), Rin[b].end(), tin[u]) - Rin[b].begin());
				else
					for (auto u : plc[b])
						ans += (lower_bound(Rin[a].begin(), Rin[a].end(), tin[u])) - (upper_bound(Rout[a].begin(), Rout[a].end(), tout[u]));
				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 9556 KB Output is correct
3 Correct 2 ms 9304 KB Output is correct
4 Correct 3 ms 9304 KB Output is correct
5 Correct 5 ms 9304 KB Output is correct
6 Correct 9 ms 9304 KB Output is correct
7 Correct 16 ms 9604 KB Output is correct
8 Correct 14 ms 9304 KB Output is correct
9 Correct 27 ms 9816 KB Output is correct
10 Correct 38 ms 9816 KB Output is correct
11 Correct 73 ms 10072 KB Output is correct
12 Correct 73 ms 10840 KB Output is correct
13 Correct 86 ms 10420 KB Output is correct
14 Correct 100 ms 11176 KB Output is correct
15 Correct 106 ms 14868 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 14924 KB Output is correct
2 Correct 550 ms 13556 KB Output is correct
3 Correct 764 ms 17756 KB Output is correct
4 Incorrect 157 ms 13424 KB Output isn't correct
5 Incorrect 252 ms 16576 KB Output isn't correct
6 Incorrect 382 ms 16412 KB Output isn't correct
7 Incorrect 513 ms 17140 KB Output isn't correct
8 Incorrect 738 ms 27348 KB Output isn't correct
9 Incorrect 1524 ms 31840 KB Output isn't correct
10 Incorrect 2816 ms 41304 KB Output isn't correct
11 Incorrect 3797 ms 35400 KB Output isn't correct
12 Incorrect 1207 ms 30232 KB Output isn't correct
13 Incorrect 1548 ms 32272 KB Output isn't correct
14 Incorrect 1803 ms 33568 KB Output isn't correct
15 Incorrect 2415 ms 42956 KB Output isn't correct
16 Incorrect 2207 ms 52780 KB Output isn't correct
17 Incorrect 2220 ms 49916 KB Output isn't correct