oj.uz

Submission #883370

# Submission time Handle Problem Language Result Execution time Memory
883370 2023-12-05T08:33:18 Z serifefedartar Regions (IOI09_regions) C++17
30 / 100
 3726 ms 52928 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])) - (upper_bound(Rin[a].begin(), Rin[a].end(), tout[u]));
				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 3 ms 9304 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 9 ms 9304 KB Output is correct
7 Correct 17 ms 9304 KB Output is correct
8 Correct 15 ms 9304 KB Output is correct
9 Correct 23 ms 9812 KB Output is correct
10 Correct 47 ms 9960 KB Output is correct
11 Correct 69 ms 10116 KB Output is correct
12 Correct 66 ms 10840 KB Output is correct
13 Correct 83 ms 10328 KB Output is correct
14 Correct 104 ms 11092 KB Output is correct
15 Correct 119 ms 14928 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 14896 KB Output is correct
2 Correct 506 ms 13456 KB Output is correct
3 Correct 683 ms 17744 KB Output is correct
4 Incorrect 163 ms 12996 KB Output isn't correct
5 Incorrect 260 ms 17060 KB Output isn't correct
6 Incorrect 337 ms 16256 KB Output isn't correct
7 Incorrect 509 ms 17308 KB Output isn't correct
8 Incorrect 745 ms 27304 KB Output isn't correct
9 Incorrect 1476 ms 31636 KB Output isn't correct
10 Incorrect 3078 ms 41536 KB Output isn't correct
11 Incorrect 3726 ms 35836 KB Output isn't correct
12 Incorrect 1130 ms 30000 KB Output isn't correct
13 Incorrect 1592 ms 32824 KB Output isn't correct
14 Incorrect 1824 ms 33828 KB Output isn't correct
15 Incorrect 2630 ms 43076 KB Output isn't correct
16 Incorrect 2307 ms 52928 KB Output isn't correct
17 Incorrect 2298 ms 49680 KB Output isn't correct