oj.uz

Submission #883354

# Submission time Handle Problem Language Result Execution time Memory
883354 2023-12-05T08:03:09 Z serifefedartar Regions (IOI09_regions) C++17
70 / 100
 3251 ms 52972 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 (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 3 ms 9288 KB Output is correct
3 Correct 3 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 11 ms 9304 KB Output is correct
7 Correct 12 ms 9304 KB Output is correct
8 Correct 16 ms 9304 KB Output is correct
9 Correct 28 ms 9816 KB Output is correct
10 Correct 40 ms 9736 KB Output is correct
11 Correct 55 ms 10124 KB Output is correct
12 Correct 69 ms 10992 KB Output is correct
13 Correct 87 ms 10668 KB Output is correct
14 Correct 107 ms 11104 KB Output is correct
15 Correct 112 ms 14928 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 14940 KB Output is correct
2 Correct 569 ms 13420 KB Output is correct
3 Correct 742 ms 17656 KB Output is correct
4 Correct 214 ms 14000 KB Output is correct
5 Correct 267 ms 16476 KB Output is correct
6 Correct 352 ms 16420 KB Output is correct
7 Correct 517 ms 16972 KB Output is correct
8 Correct 860 ms 26496 KB Output is correct
9 Correct 1744 ms 31500 KB Output is correct
10 Correct 3085 ms 40760 KB Output is correct
11 Correct 3251 ms 35800 KB Output is correct
12 Incorrect 907 ms 29160 KB Output isn't correct
13 Incorrect 1376 ms 32972 KB Output isn't correct
14 Incorrect 1631 ms 33468 KB Output isn't correct
15 Incorrect 2302 ms 42752 KB Output isn't correct
16 Incorrect 2368 ms 52972 KB Output isn't correct
17 Incorrect 2270 ms 49780 KB Output isn't correct