답안 #478215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478215	2021-10-06T13:41:29 Z	Abrar_Al_Samit	Regions (IOI09_regions)	C++17	컴파일 오류	0 ms	0 KB

regions

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
const int B = 447;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], stwho[MX];
int index[MX], timer=1;
long long prep[B][25001];
	
void Flat(int v, int p) {
	stwho[timer] = v;
	st[v] = timer++;
	region[H[v]].push_back(st[v]);
	for(auto to : g[v]) if(to!=p) {
		Flat(to, v);
	}
	en[v] = timer-1;
}
void DFS(int v, int p, int reg, int cnt) {
	if(H[v]==reg) ++cnt;
	else prep[index[reg]][H[v]] += cnt;
	for(auto u : g[v]) if(u!=p) {
		DFS(u, v, reg, cnt);
	}
}
int main() {
	cin >> N >> R >> Q;
	cin >> H[1];
	for(int i=2; i<=N; ++i) {
		int p; cin >> p >> H[i];
		g[p].push_back(i);
	}
	Flat(1, 1);
	int cur = 0;
	for(int i=1; i<=R; ++i) if(region[i].size()>B) {
		index[i] = cur++;
		DFS(1, 1, i, 0);
	}
	// O(Q(rootNlogN + logR))
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		long long ans = 0;
		if(region[r1].size()>B) {
			ans = prep[index[r1]][r2];
		} else {
			for(auto p1 : region[r1]) {
				auto it = upper_bound(region[r2].begin(), region[r2].end(), en[stwho[p1]]);
				auto it2 = lower_bound(region[r2].begin(), region[r2].end(), p1);
				ans += it-it2; 
			}
		}
		assert(ans>=0);
		cout << ans << endl;
	}
	return 0;
}

Compilation message

regions.cpp:9:13: error: 'int index [200005]' redeclared as different kind of entity
    9 | int index[MX], timer=1;
      |             ^
In file included from /usr/include/string.h:432,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from regions.cpp:2:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
regions.cpp: In function 'void DFS(int, int, int, int)':
regions.cpp:23:17: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   23 |  else prep[index[reg]][H[v]] += cnt;
      |                 ^
regions.cpp: In function 'int main()':
regions.cpp:38:8: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   38 |   index[i] = cur++;
      |        ^
regions.cpp:47:20: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
   47 |    ans = prep[index[r1]][r2];
      |                    ^