oj.uz

Submission #883344

# Submission time Handle Problem Language Result Execution time Memory
883344 2023-12-05T07:56:39 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 1357 ms 50600 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];
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];
	for (int i = 2; i <= N; i++) {
		int S;
		cin >> S >> reg[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() < Rin[b].size())
					ans = (upper_bound(Rin[b].begin(), Rin[b].end(), tout[a]) - Rin[b].begin()) - (lower_bound(Rin[b].begin(), Rin[b].end(), tin[a]) - 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 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 4 ms 8536 KB Output is correct
6 Correct 10 ms 8792 KB Output is correct
7 Correct 14 ms 8792 KB Output is correct
8 Correct 18 ms 8792 KB Output is correct
9 Correct 25 ms 9404 KB Output is correct
10 Correct 39 ms 9300 KB Output is correct
11 Correct 71 ms 9560 KB Output is correct
12 Correct 65 ms 10224 KB Output is correct
13 Correct 69 ms 9644 KB Output is correct
14 Correct 110 ms 10328 KB Output is correct
15 Correct 125 ms 14332 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 14120 KB Output is correct
2 Correct 513 ms 12600 KB Output is correct
3 Correct 754 ms 16572 KB Output is correct
4 Incorrect 143 ms 13384 KB Output isn't correct
5 Incorrect 239 ms 16864 KB Output isn't correct
6 Incorrect 351 ms 15588 KB Output isn't correct
7 Incorrect 545 ms 15916 KB Output isn't correct
8 Incorrect 536 ms 26200 KB Output isn't correct
9 Incorrect 859 ms 29776 KB Output isn't correct
10 Incorrect 1151 ms 38780 KB Output isn't correct
11 Incorrect 1357 ms 32716 KB Output isn't correct
12 Incorrect 554 ms 28776 KB Output isn't correct
13 Incorrect 744 ms 31016 KB Output isn't correct
14 Incorrect 922 ms 32236 KB Output isn't correct
15 Incorrect 1150 ms 40200 KB Output isn't correct
16 Incorrect 1241 ms 50600 KB Output isn't correct
17 Incorrect 1282 ms 48360 KB Output isn't correct