oj.uz

Submission #883393

# Submission time Handle Problem Language Result Execution time Memory
883393 2023-12-05T08:55:13 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3762 ms 52944 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 4 ms 9304 KB Output is correct
4 Correct 3 ms 9304 KB Output is correct
5 Correct 5 ms 9140 KB Output is correct
6 Correct 9 ms 9304 KB Output is correct
7 Correct 14 ms 9304 KB Output is correct
8 Correct 17 ms 9616 KB Output is correct
9 Correct 26 ms 9816 KB Output is correct
10 Correct 40 ms 9816 KB Output is correct
11 Correct 53 ms 10072 KB Output is correct
12 Correct 63 ms 10980 KB Output is correct
13 Correct 84 ms 10540 KB Output is correct
14 Correct 119 ms 11072 KB Output is correct
15 Correct 122 ms 14824 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 15100 KB Output is correct
2 Correct 526 ms 13644 KB Output is correct
3 Correct 741 ms 17640 KB Output is correct
4 Incorrect 191 ms 13468 KB Output isn't correct
5 Incorrect 236 ms 16264 KB Output isn't correct
6 Incorrect 375 ms 16172 KB Output isn't correct
7 Incorrect 527 ms 17012 KB Output isn't correct
8 Incorrect 734 ms 27408 KB Output isn't correct
9 Incorrect 1435 ms 31856 KB Output isn't correct
10 Incorrect 2980 ms 41380 KB Output isn't correct
11 Incorrect 3762 ms 36240 KB Output isn't correct
12 Incorrect 1136 ms 29912 KB Output isn't correct
13 Incorrect 1442 ms 32756 KB Output isn't correct
14 Incorrect 1725 ms 34188 KB Output isn't correct
15 Incorrect 2319 ms 43452 KB Output isn't correct
16 Incorrect 2214 ms 52944 KB Output isn't correct
17 Incorrect 2100 ms 50428 KB Output isn't correct