Submission #904287

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
904287	2024-01-12T02:30:06 Z	IBory	Regions (IOI09_regions)	C++17	55 / 100	8000 ms	58012 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);
		}
		printf("%d\n", ans);
		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	4 ms	11352 KB	Output is correct
2	Correct	3 ms	11352 KB	Output is correct
3	Correct	4 ms	11352 KB	Output is correct
4	Correct	6 ms	11352 KB	Output is correct
5	Correct	7 ms	11764 KB	Output is correct
6	Correct	12 ms	11608 KB	Output is correct
7	Correct	20 ms	11608 KB	Output is correct
8	Correct	21 ms	11608 KB	Output is correct
9	Correct	33 ms	11864 KB	Output is correct
10	Correct	71 ms	11964 KB	Output is correct
11	Correct	104 ms	12036 KB	Output is correct
12	Correct	105 ms	12408 KB	Output is correct
13	Correct	169 ms	12292 KB	Output is correct
14	Correct	261 ms	12752 KB	Output is correct
15	Correct	315 ms	14548 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8010 ms	16312 KB	Time limit exceeded
2	Execution timed out	8020 ms	15116 KB	Time limit exceeded
3	Execution timed out	8007 ms	17892 KB	Time limit exceeded
4	Correct	280 ms	12784 KB	Output is correct
5	Correct	310 ms	13832 KB	Output is correct
6	Correct	1375 ms	13512 KB	Output is correct
7	Correct	1981 ms	14356 KB	Output is correct
8	Correct	1934 ms	17984 KB	Output is correct
9	Correct	2943 ms	18808 KB	Output is correct
10	Correct	5094 ms	22192 KB	Output is correct
11	Correct	5341 ms	18124 KB	Output is correct
12	Execution timed out	8042 ms	22880 KB	Time limit exceeded
13	Execution timed out	8042 ms	23004 KB	Time limit exceeded
14	Execution timed out	8054 ms	48044 KB	Time limit exceeded
15	Execution timed out	8005 ms	27904 KB	Time limit exceeded
16	Execution timed out	8042 ms	33420 KB	Time limit exceeded
17	Execution timed out	8048 ms	58012 KB	Time limit exceeded