oj.uz

Submission #883402

# Submission time Handle Problem Language Result Execution time Memory
883402 2023-12-05T09:00:10 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3735 ms 52704 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 = 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 2 ms 9304 KB Output is correct
3 Correct 3 ms 9304 KB Output is correct
4 Correct 4 ms 9304 KB Output is correct
5 Correct 5 ms 9304 KB Output is correct
6 Correct 12 ms 9556 KB Output is correct
7 Correct 13 ms 9304 KB Output is correct
8 Correct 19 ms 9304 KB Output is correct
9 Correct 26 ms 9816 KB Output is correct
10 Correct 47 ms 9928 KB Output is correct
11 Correct 52 ms 10328 KB Output is correct
12 Correct 84 ms 10840 KB Output is correct
13 Correct 79 ms 10328 KB Output is correct
14 Correct 92 ms 11192 KB Output is correct
15 Correct 108 ms 14940 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 15044 KB Output is correct
2 Correct 493 ms 13632 KB Output is correct
3 Correct 686 ms 17744 KB Output is correct
4 Incorrect 202 ms 13876 KB Output isn't correct
5 Incorrect 270 ms 16768 KB Output isn't correct
6 Incorrect 362 ms 16328 KB Output isn't correct
7 Incorrect 578 ms 17304 KB Output isn't correct
8 Incorrect 779 ms 27120 KB Output isn't correct
9 Incorrect 1415 ms 31652 KB Output isn't correct
10 Incorrect 3153 ms 40704 KB Output isn't correct
11 Incorrect 3735 ms 35408 KB Output isn't correct
12 Incorrect 1093 ms 29616 KB Output isn't correct
13 Incorrect 1560 ms 32320 KB Output isn't correct
14 Incorrect 1757 ms 33960 KB Output isn't correct
15 Incorrect 2718 ms 42480 KB Output isn't correct
16 Incorrect 2535 ms 52704 KB Output isn't correct
17 Incorrect 2381 ms 49528 KB Output isn't correct