Submission #904286

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
904286	2024-01-12T02:29:46 Z	IBory	Regions (IOI09_regions)	C++17	65 / 100	8000 ms	57752 KB

regions

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 200007, CUT = 500;
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;
	scanf("%d %d %d", &N, &M, &Q);
	scanf("%d", &C[1]);
	R[C[1]].push_back(1);
	for (int i = 2; i <= N; ++i) {
		int p;
		scanf("%d %d", &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;
		scanf("%d %d", &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';
		fflush(stdout);
	}
	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);
      |        ^~~
regions.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d", &C[1]);
      |  ~~~~~^~~~~~~~~~~~~
regions.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d %d", &p, &C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d %d", &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	4 ms	11352 KB	Output is correct
4	Correct	6 ms	11508 KB	Output is correct
5	Correct	6 ms	11352 KB	Output is correct
6	Correct	13 ms	11608 KB	Output is correct
7	Correct	20 ms	11608 KB	Output is correct
8	Correct	21 ms	11860 KB	Output is correct
9	Correct	29 ms	11864 KB	Output is correct
10	Correct	60 ms	12128 KB	Output is correct
11	Correct	98 ms	12120 KB	Output is correct
12	Correct	117 ms	12504 KB	Output is correct
13	Correct	145 ms	12292 KB	Output is correct
14	Correct	265 ms	12584 KB	Output is correct
15	Correct	291 ms	14344 KB	Output is correct

Subtask #2

50.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7445 ms	16152 KB	Output is correct
2	Correct	7574 ms	15116 KB	Output is correct
3	Execution timed out	8036 ms	18012 KB	Time limit exceeded
4	Correct	283 ms	12784 KB	Output is correct
5	Correct	327 ms	14080 KB	Output is correct
6	Correct	1469 ms	13724 KB	Output is correct
7	Correct	1891 ms	14348 KB	Output is correct
8	Correct	1818 ms	17772 KB	Output is correct
9	Correct	3116 ms	18648 KB	Output is correct
10	Correct	5558 ms	22184 KB	Output is correct
11	Correct	5445 ms	18168 KB	Output is correct
12	Execution timed out	8086 ms	22844 KB	Time limit exceeded
13	Execution timed out	8082 ms	22872 KB	Time limit exceeded
14	Execution timed out	8048 ms	47952 KB	Time limit exceeded
15	Execution timed out	8071 ms	27700 KB	Time limit exceeded
16	Execution timed out	8036 ms	33308 KB	Time limit exceeded
17	Execution timed out	8064 ms	57752 KB	Time limit exceeded