oj.uz

Submission #904276

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

const int MAX = 200007, CUT = 1000;
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 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 7 ms 11352 KB Output is correct
5 Correct 6 ms 11352 KB Output is correct
6 Correct 13 ms 11388 KB Output is correct
7 Correct 23 ms 11608 KB Output is correct
8 Correct 23 ms 11608 KB Output is correct
9 Correct 34 ms 11864 KB Output is correct
10 Correct 62 ms 11864 KB Output is correct
11 Correct 98 ms 11984 KB Output is correct
12 Correct 119 ms 12444 KB Output is correct
13 Correct 155 ms 12448 KB Output is correct
14 Correct 263 ms 12564 KB Output is correct
15 Correct 302 ms 14348 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 7570 ms 16236 KB Output is correct
2 Execution timed out 8035 ms 15112 KB Time limit exceeded
3 Execution timed out 8077 ms 17844 KB Time limit exceeded
4 Correct 289 ms 12756 KB Output is correct
5 Correct 331 ms 13820 KB Output is correct
6 Correct 1356 ms 13492 KB Output is correct
7 Correct 1956 ms 14344 KB Output is correct
8 Correct 2053 ms 17748 KB Output is correct
9 Correct 3344 ms 18640 KB Output is correct
10 Correct 5436 ms 21932 KB Output is correct
11 Correct 5159 ms 18124 KB Output is correct
12 Execution timed out 8055 ms 22880 KB Time limit exceeded
13 Execution timed out 8039 ms 22900 KB Time limit exceeded
14 Execution timed out 8054 ms 36892 KB Time limit exceeded
15 Execution timed out 8042 ms 27900 KB Time limit exceeded
16 Execution timed out 8074 ms 33452 KB Time limit exceeded
17 Execution timed out 8042 ms 46472 KB Time limit exceeded