oj.uz

Submission #883384

# Submission time Handle Problem Language Result Execution time Memory
883384 2023-12-05T08:47:48 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3713 ms 53016 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(), tout[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 3 ms 9136 KB Output is correct
5 Correct 4 ms 9304 KB Output is correct
6 Correct 12 ms 9304 KB Output is correct
7 Correct 16 ms 9352 KB Output is correct
8 Correct 17 ms 9560 KB Output is correct
9 Correct 28 ms 9816 KB Output is correct
10 Correct 46 ms 9968 KB Output is correct
11 Correct 53 ms 10324 KB Output is correct
12 Correct 75 ms 11096 KB Output is correct
13 Correct 88 ms 10536 KB Output is correct
14 Correct 94 ms 11096 KB Output is correct
15 Correct 119 ms 14872 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 15056 KB Output is correct
2 Correct 519 ms 13644 KB Output is correct
3 Correct 753 ms 17600 KB Output is correct
4 Incorrect 170 ms 13256 KB Output isn't correct
5 Incorrect 248 ms 16944 KB Output isn't correct
6 Incorrect 388 ms 15968 KB Output isn't correct
7 Incorrect 538 ms 17040 KB Output isn't correct
8 Incorrect 735 ms 27128 KB Output isn't correct
9 Incorrect 1561 ms 31564 KB Output isn't correct
10 Incorrect 2920 ms 41272 KB Output isn't correct
11 Incorrect 3713 ms 35644 KB Output isn't correct
12 Incorrect 1155 ms 29980 KB Output isn't correct
13 Incorrect 1678 ms 32288 KB Output isn't correct
14 Incorrect 1872 ms 33880 KB Output isn't correct
15 Incorrect 2446 ms 42660 KB Output isn't correct
16 Incorrect 2312 ms 53016 KB Output isn't correct
17 Incorrect 2141 ms 49696 KB Output isn't correct