oj.uz

Submission #883377

# Submission time Handle Problem Language Result Execution time Memory
883377 2023-12-05T08:43:25 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3847 ms 52612 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 (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()) - (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]) - 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 9304 KB Output is correct
4 Correct 3 ms 9304 KB Output is correct
5 Correct 7 ms 9304 KB Output is correct
6 Correct 12 ms 9304 KB Output is correct
7 Correct 15 ms 9304 KB Output is correct
8 Correct 17 ms 9304 KB Output is correct
9 Correct 23 ms 9816 KB Output is correct
10 Correct 37 ms 9816 KB Output is correct
11 Correct 69 ms 10324 KB Output is correct
12 Correct 68 ms 10840 KB Output is correct
13 Correct 102 ms 10484 KB Output is correct
14 Correct 79 ms 11096 KB Output is correct
15 Correct 106 ms 15016 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 14920 KB Output is correct
2 Correct 516 ms 13656 KB Output is correct
3 Correct 787 ms 17636 KB Output is correct
4 Incorrect 174 ms 13656 KB Output isn't correct
5 Incorrect 254 ms 16628 KB Output isn't correct
6 Incorrect 346 ms 16236 KB Output isn't correct
7 Incorrect 520 ms 16832 KB Output isn't correct
8 Incorrect 717 ms 27220 KB Output isn't correct
9 Incorrect 1473 ms 31428 KB Output isn't correct
10 Incorrect 3061 ms 41140 KB Output isn't correct
11 Incorrect 3847 ms 35580 KB Output isn't correct
12 Incorrect 1077 ms 29672 KB Output isn't correct
13 Incorrect 1667 ms 32348 KB Output isn't correct
14 Incorrect 1785 ms 33376 KB Output isn't correct
15 Incorrect 2488 ms 42984 KB Output isn't correct
16 Incorrect 2453 ms 52612 KB Output isn't correct
17 Incorrect 2371 ms 50396 KB Output isn't correct