oj.uz

Submission #883390

# Submission time Handle Problem Language Result Execution time Memory
883390 2023-12-05T08:53:02 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3675 ms 52796 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
					for (auto u : plc[b])
						ans += Rin[a].size() - (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 3 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 2 ms 9304 KB Output is correct
4 Correct 3 ms 9304 KB Output is correct
5 Correct 5 ms 9304 KB Output is correct
6 Correct 10 ms 9304 KB Output is correct
7 Correct 14 ms 9304 KB Output is correct
8 Correct 17 ms 9304 KB Output is correct
9 Correct 25 ms 9816 KB Output is correct
10 Correct 53 ms 9816 KB Output is correct
11 Correct 58 ms 10092 KB Output is correct
12 Correct 62 ms 10988 KB Output is correct
13 Correct 88 ms 10328 KB Output is correct
14 Correct 86 ms 11024 KB Output is correct
15 Correct 124 ms 15044 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 15140 KB Output is correct
2 Correct 549 ms 13652 KB Output is correct
3 Correct 718 ms 17792 KB Output is correct
4 Incorrect 175 ms 14000 KB Output isn't correct
5 Incorrect 240 ms 16028 KB Output isn't correct
6 Incorrect 377 ms 15660 KB Output isn't correct
7 Incorrect 564 ms 16900 KB Output isn't correct
8 Incorrect 727 ms 27420 KB Output isn't correct
9 Incorrect 1486 ms 31412 KB Output isn't correct
10 Incorrect 2817 ms 41264 KB Output isn't correct
11 Incorrect 3675 ms 35820 KB Output isn't correct
12 Incorrect 1076 ms 29920 KB Output isn't correct
13 Incorrect 1578 ms 32796 KB Output isn't correct
14 Incorrect 1812 ms 34076 KB Output isn't correct
15 Incorrect 2486 ms 42824 KB Output isn't correct
16 Incorrect 2269 ms 52796 KB Output isn't correct
17 Incorrect 2275 ms 50080 KB Output isn't correct