oj.uz

Submission #883346

# Submission time Handle Problem Language Result Execution time Memory
883346 2023-12-05T07:58:51 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 1923 ms 51832 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;
				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 9556 KB Output is correct
3 Correct 3 ms 9304 KB Output is correct
4 Correct 4 ms 9304 KB Output is correct
5 Correct 5 ms 9304 KB Output is correct
6 Correct 8 ms 9304 KB Output is correct
7 Correct 16 ms 9304 KB Output is correct
8 Correct 18 ms 9304 KB Output is correct
9 Correct 23 ms 9816 KB Output is correct
10 Correct 41 ms 9720 KB Output is correct
11 Correct 56 ms 10328 KB Output is correct
12 Correct 70 ms 10856 KB Output is correct
13 Correct 93 ms 10328 KB Output is correct
14 Correct 87 ms 11068 KB Output is correct
15 Correct 127 ms 15060 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 14956 KB Output is correct
2 Correct 461 ms 13592 KB Output is correct
3 Correct 725 ms 17680 KB Output is correct
4 Incorrect 138 ms 13688 KB Output isn't correct
5 Incorrect 213 ms 16936 KB Output isn't correct
6 Incorrect 341 ms 16248 KB Output isn't correct
7 Incorrect 479 ms 16824 KB Output isn't correct
8 Incorrect 565 ms 27148 KB Output isn't correct
9 Incorrect 924 ms 31264 KB Output isn't correct
10 Incorrect 1097 ms 40072 KB Output isn't correct
11 Incorrect 1339 ms 34840 KB Output isn't correct
12 Incorrect 817 ms 29768 KB Output isn't correct
13 Incorrect 1045 ms 32312 KB Output isn't correct
14 Incorrect 1228 ms 33448 KB Output isn't correct
15 Incorrect 1678 ms 41596 KB Output isn't correct
16 Incorrect 1923 ms 51832 KB Output isn't correct
17 Incorrect 1554 ms 49576 KB Output isn't correct