oj.uz

답안 #904287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
904287 2024-01-12T02:30:06 Z IBory Regions (IOI09_regions) C++17
55 / 100
 8000 ms 58012 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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