제출 #904286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904286		IBory	Regions (IOI09_regions)	C++17	65 / 100	8086 ms	57752 KiB

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 50 / 85