oj.uz

Submission #904277

# Submission time Handle Problem Language Result Execution time Memory
904277 2024-01-12T02:22:41 Z IBory Regions (IOI09_regions) C++14
55 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 200007, CUT = 200;
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 3 ms 11604 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 6 ms 11352 KB Output is correct
4 Correct 5 ms 11352 KB Output is correct
5 Correct 7 ms 11352 KB Output is correct
6 Correct 14 ms 11608 KB Output is correct
7 Correct 22 ms 11608 KB Output is correct
8 Correct 23 ms 11608 KB Output is correct
9 Correct 30 ms 11864 KB Output is correct
10 Correct 67 ms 11864 KB Output is correct
11 Correct 98 ms 11968 KB Output is correct
12 Correct 106 ms 12328 KB Output is correct
13 Correct 182 ms 12284 KB Output is correct
14 Correct 292 ms 12796 KB Output is correct
15 Correct 314 ms 16020 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4467 ms 17400 KB Output is correct
2 Correct 765 ms 17152 KB Output is correct
3 Execution timed out 8045 ms 17964 KB Time limit exceeded
4 Correct 302 ms 12780 KB Output is correct
5 Correct 327 ms 13792 KB Output is correct
6 Correct 739 ms 40904 KB Output is correct
7 Correct 1717 ms 46536 KB Output is correct
8 Correct 2141 ms 82752 KB Output is correct
9 Correct 4580 ms 113704 KB Output is correct
10 Runtime error 877 ms 131072 KB Execution killed with signal 9
11 Runtime error 1570 ms 131072 KB Execution killed with signal 9
12 Runtime error 2928 ms 131072 KB Execution killed with signal 9
13 Runtime error 2594 ms 131072 KB Execution killed with signal 9
14 Execution timed out 8047 ms 47960 KB Time limit exceeded
15 Execution timed out 8053 ms 27828 KB Time limit exceeded
16 Runtime error 1006 ms 131072 KB Execution killed with signal 9
17 Execution timed out 8054 ms 58164 KB Time limit exceeded