oj.uz

Submission #883349

# Submission time Handle Problem Language Result Execution time Memory
883349 2023-12-05T08:00:48 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 1921 ms 52212 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;
	Rout[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 (Rin[a].size() < 510)
					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 {

				}
				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 4 ms 9304 KB Output is correct
6 Correct 10 ms 9304 KB Output is correct
7 Correct 15 ms 9328 KB Output is correct
8 Correct 20 ms 9304 KB Output is correct
9 Correct 25 ms 9816 KB Output is correct
10 Correct 39 ms 9816 KB Output is correct
11 Correct 57 ms 10484 KB Output is correct
12 Correct 72 ms 10840 KB Output is correct
13 Correct 78 ms 10448 KB Output is correct
14 Correct 82 ms 10936 KB Output is correct
15 Correct 98 ms 14924 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 14948 KB Output is correct
2 Correct 557 ms 13656 KB Output is correct
3 Correct 737 ms 17700 KB Output is correct
4 Incorrect 138 ms 13648 KB Output isn't correct
5 Incorrect 198 ms 16956 KB Output isn't correct
6 Incorrect 362 ms 15704 KB Output isn't correct
7 Incorrect 551 ms 16348 KB Output isn't correct
8 Incorrect 584 ms 26772 KB Output isn't correct
9 Incorrect 1004 ms 31316 KB Output isn't correct
10 Incorrect 1151 ms 40056 KB Output isn't correct
11 Incorrect 1421 ms 34892 KB Output isn't correct
12 Incorrect 825 ms 29516 KB Output isn't correct
13 Incorrect 1126 ms 32048 KB Output isn't correct
14 Incorrect 1153 ms 33500 KB Output isn't correct
15 Incorrect 1727 ms 42552 KB Output isn't correct
16 Incorrect 1921 ms 52212 KB Output isn't correct
17 Incorrect 1606 ms 49944 KB Output isn't correct