oj.uz

Submission #883375

# Submission time Handle Problem Language Result Execution time Memory
883375 2023-12-05T08:40:02 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3582 ms 52584 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(Rin[a].begin(), Rin[a].end(), tout[u]) - Rin[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 9292 KB Output is correct
3 Correct 2 ms 9304 KB Output is correct
4 Correct 3 ms 9304 KB Output is correct
5 Correct 4 ms 9304 KB Output is correct
6 Correct 10 ms 9304 KB Output is correct
7 Correct 15 ms 9304 KB Output is correct
8 Correct 20 ms 9304 KB Output is correct
9 Correct 24 ms 9816 KB Output is correct
10 Correct 48 ms 9816 KB Output is correct
11 Correct 45 ms 10328 KB Output is correct
12 Correct 64 ms 10840 KB Output is correct
13 Correct 92 ms 10468 KB Output is correct
14 Correct 97 ms 11196 KB Output is correct
15 Correct 105 ms 15036 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 14928 KB Output is correct
2 Correct 493 ms 13592 KB Output is correct
3 Correct 765 ms 17740 KB Output is correct
4 Incorrect 169 ms 13600 KB Output isn't correct
5 Incorrect 223 ms 16936 KB Output isn't correct
6 Incorrect 322 ms 16160 KB Output isn't correct
7 Incorrect 508 ms 16600 KB Output isn't correct
8 Incorrect 706 ms 27144 KB Output isn't correct
9 Incorrect 1445 ms 31848 KB Output isn't correct
10 Incorrect 2899 ms 41396 KB Output isn't correct
11 Incorrect 3582 ms 35612 KB Output isn't correct
12 Incorrect 1012 ms 29744 KB Output isn't correct
13 Incorrect 1465 ms 32860 KB Output isn't correct
14 Incorrect 1660 ms 33616 KB Output isn't correct
15 Incorrect 2419 ms 42952 KB Output isn't correct
16 Incorrect 2113 ms 52584 KB Output isn't correct
17 Incorrect 2122 ms 49988 KB Output isn't correct