Submission #652552

#	Time	Username	Problem	Language	Result	Execution time	Memory
652552		rxlfd314	Regions (IOI09_regions)	C++17	0 / 100	489 ms	29032 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define cerr if (false) cout
constexpr int mxN = 2e5, mxR = 25e3;
int N, R, Q, rgn[mxN];
vector<int> adj[mxN], rgnLst[mxR];
int tin[mxN], tout[mxN], timer;
void getTimes(int f) {
	tin[f] = timer++;
	for (int nf : adj[f]) {
		getTimes(nf);
	}
	tout[f] = timer - 1;
}
int acnt[mxN];
void getacnt(int f, int t, int cur = 0) {
	acnt[f] = cur;
	cur += rgn[f] == t;
	for (int nf : adj[f]) {
		getacnt(nf, t, cur);
	}
}
bool comp(int a, int b) {
	return tin[a] < tin[b];
}
signed main() {
#ifdef cerr
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
#endif
	cin >> N >> R >> Q >> rgn[0];
	rgnLst[--rgn[0]].push_back(0);
	for (int i = 1, a; i < N; i++) {
		cin >> a >> rgn[i];
		adj[--a].push_back(i);
		rgnLst[--rgn[i]].push_back(i);
	}
	getTimes(0);
	vector<int> big;
	constexpr int BSZ = 447;
	for (int i = 0; i < R; i++) {
		if (rgnLst[i].size() > BSZ) {
			big.push_back(i);
		}
		sort(rgnLst[i].begin(), rgnLst[i].end(), comp);
	}
	int ans[big.size()][R][2], psum[N];
	memset(ans, 0, sizeof(ans));
	for (int i = 0; i < big.size(); i++) { // O(sqrt(N) * (4 * N + R))
		getacnt(0, big[i]);
		memset(psum, 0, sizeof(psum));
		for (int j : rgnLst[big[i]]) {
			psum[tin[j]]++;
		}
		for (int j = 1; j < N; j++) {
			psum[j] += psum[j-1];
		}
		for (int j = 0; j < R; j++) {
			if (j == big[i]) continue;
			for (int k : rgnLst[j]) {
				ans[i][j][0] += acnt[k];
				ans[i][j][1] += psum[tout[k]] - (tin[k] > 0 ? psum[tin[k]-1] : 0);
			}
		}
	}
	for (int q = 0, a, b; q < Q; q++) { // O(N * sqrt(N) * log_2(sqrt(N)))
		cin >> a >> b;
		a--, b--;
		if (rgnLst[a].size() > BSZ) {
			cout << ans[lower_bound(big.begin(),big.end(),a)-big.begin()][b][0] << '\n';
		} else if (rgnLst[b].size() > BSZ) {
			cout << ans[lower_bound(big.begin(),big.end(),b)-big.begin()][a][1] << '\n';
		} else {
			ll res = 0;
			for (int i : rgnLst[a]) {
				res += upper_bound(rgnLst[b].begin(), rgnLst[b].end(), tout[i], comp) - lower_bound(rgnLst[b].begin(), rgnLst[b].end(), tin[i], comp); 
			}
			cout << res << '\n';
		}
	}
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < big.size(); i++) { // O(sqrt(N) * (4 * N + R))
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85