oj.uz

Submission #904275

# Submission time Handle Problem Language Result Execution time Memory
904275 2024-01-12T02:16:44 Z IBory Regions (IOI09_regions) C++17
65 / 100
 8000 ms 54408 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 200007, CUT = 600;
vector<int> G[MAX], R[MAX];
int C[MAX], in[MAX], out[MAX], cnt[MAX], dn;

void DFS(int cur) {
	in[cur] = ++dn;
	for (int next : G[cur]) DFS(next);
	out[cur] = dn;
}

void DFS2(int cur, int col, int d) {
	if (C[cur] == col) d++;
	else cnt[C[cur]] += d;
	for (int next : G[cur]) DFS2(next, col, d);
}

struct BIT {
	int T[MAX];
	void Update(int i, int v) {
		for (; i < MAX; i += i & -i) T[i] += v;
	}
	int Query(int L, int R) {
		int ret = 0; L--;
		for (; R; R -= R & -R) ret += T[R];
		for (; L; L -= L & -L) ret -= T[L];
		return ret;
	}
} T;

int Process(int a, int b) {
	int ret = 0;
	for (int n : R[a]) ret += T.Query(in[n], out[n]);
	return ret;
}

int main() {
	int N, M, Q;
	cin >> N >> M >> Q;
	cin >> C[1];
	R[C[1]].push_back(1);
	for (int i = 2; i <= N; ++i) {
		int p;
		cin >> p >> C[i];
		R[C[i]].push_back(i);
		G[p].push_back(i);
	}

	DFS(1);
	map<pii, int> pre;
	vector<int> big;
	for (int i = 1; i <= M; ++i) if (R[i].size() > CUT) big.push_back(i);

	for (int b : big) {
		for (int n : R[b]) T.Update(in[n], 1);
		for (int a = 1; a <= M; ++a) {
			if (a == b) continue;
			int cnt = Process(a, b);
		}
		for (int n : R[b]) T.Update(in[n], -1);
	}

	for (int a : big) {
		memset(cnt, 0, sizeof(cnt));
		DFS2(1, a, 0);
		for (int b = 1; b <= M; ++b) {
			if (a == b) continue;
			pre[{a, b}] = cnt[b];
		}
	}

	while (Q--) {
		int a, b, ans = -1;
		cin >> a >> b;
		if (pre.find({a, b}) != pre.end()) ans = pre[{a, b}];
		else {
			for (int n : R[b]) T.Update(in[n], 1);
			ans = Process(a, b);
			for (int n : R[b]) T.Update(in[n], -1);
		}
		cout << ans << '\n';
		cout.flush();
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:61:8: warning: unused variable 'cnt' [-Wunused-variable]
   61 |    int cnt = Process(a, b);
      |        ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11352 KB Output is correct
2 Correct 4 ms 11352 KB Output is correct
3 Correct 5 ms 11352 KB Output is correct
4 Correct 5 ms 11352 KB Output is correct
5 Correct 9 ms 11352 KB Output is correct
6 Correct 12 ms 11608 KB Output is correct
7 Correct 17 ms 11608 KB Output is correct
8 Correct 21 ms 11608 KB Output is correct
9 Correct 38 ms 11864 KB Output is correct
10 Correct 62 ms 11864 KB Output is correct
11 Correct 91 ms 12120 KB Output is correct
12 Correct 117 ms 12416 KB Output is correct
13 Correct 167 ms 12284 KB Output is correct
14 Correct 251 ms 12672 KB Output is correct
15 Correct 304 ms 14232 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 7376 ms 16180 KB Output is correct
2 Correct 7533 ms 14988 KB Output is correct
3 Execution timed out 8019 ms 17904 KB Time limit exceeded
4 Correct 294 ms 12772 KB Output is correct
5 Correct 288 ms 13820 KB Output is correct
6 Correct 1211 ms 13688 KB Output is correct
7 Correct 1752 ms 14344 KB Output is correct
8 Correct 1676 ms 17800 KB Output is correct
9 Correct 2711 ms 18652 KB Output is correct
10 Correct 4429 ms 21936 KB Output is correct
11 Correct 4616 ms 18124 KB Output is correct
12 Execution timed out 8018 ms 22720 KB Time limit exceeded
13 Execution timed out 8028 ms 23192 KB Time limit exceeded
14 Execution timed out 8087 ms 43052 KB Time limit exceeded
15 Execution timed out 8016 ms 28232 KB Time limit exceeded
16 Execution timed out 8095 ms 33420 KB Time limit exceeded
17 Execution timed out 8080 ms 54408 KB Time limit exceeded