oj.uz

Submission #883371

# Submission time Handle Problem Language Result Execution time Memory
883371 2023-12-05T08:34:52 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3651 ms 52552 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
					// tin[A] <= tin[B] && tout[B] <= tout[A]
					// B belli. tin küçük olanlar => lower_bound
					// tout küçükse tin kesin küçüktür
					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(), tout[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 9556 KB Output is correct
3 Correct 3 ms 9304 KB Output is correct
4 Correct 3 ms 9556 KB Output is correct
5 Correct 4 ms 9304 KB Output is correct
6 Correct 9 ms 9304 KB Output is correct
7 Correct 13 ms 9304 KB Output is correct
8 Correct 17 ms 9304 KB Output is correct
9 Correct 28 ms 9816 KB Output is correct
10 Correct 40 ms 10072 KB Output is correct
11 Correct 60 ms 10328 KB Output is correct
12 Correct 75 ms 10760 KB Output is correct
13 Correct 77 ms 10328 KB Output is correct
14 Correct 79 ms 11104 KB Output is correct
15 Correct 100 ms 15224 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 14928 KB Output is correct
2 Correct 507 ms 13656 KB Output is correct
3 Correct 809 ms 17972 KB Output is correct
4 Incorrect 196 ms 13208 KB Output isn't correct
5 Incorrect 243 ms 17076 KB Output isn't correct
6 Incorrect 339 ms 16228 KB Output isn't correct
7 Incorrect 488 ms 17052 KB Output isn't correct
8 Incorrect 676 ms 27172 KB Output isn't correct
9 Incorrect 1463 ms 32088 KB Output isn't correct
10 Incorrect 2796 ms 41344 KB Output isn't correct
11 Incorrect 3651 ms 35880 KB Output isn't correct
12 Incorrect 1057 ms 30364 KB Output isn't correct
13 Incorrect 1499 ms 33000 KB Output isn't correct
14 Incorrect 1745 ms 33436 KB Output isn't correct
15 Incorrect 2366 ms 43112 KB Output isn't correct
16 Incorrect 2227 ms 52552 KB Output isn't correct
17 Incorrect 2205 ms 49888 KB Output isn't correct