Submission #1275962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275962		sonarcht	Regions (IOI09_regions)	C++20	100 / 100	3073 ms	30604 KiB

regions

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef map<ll,ll> mll;
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll maxn = 200001, maxr = 25001, maxb = 500, mod = 1e9 + 7;
ll n, m, r, k, q, ans, a[maxn], block = 500;

vll adj[maxn];
vll heavy;
ll get_rank(ll x) {
	return lower_bound(heavy.begin(), heavy.end(), x) - heavy.begin();
}

vll v1[maxr], v2[maxr];
ll tin[maxn], tout[maxn], tour[maxn], timer = 0, freq[maxb];
ll pre[maxb][maxr];
void dfs(ll p, ll u) {
	tin[u] = ++timer;
	tour[timer] = u;
	for (int i = 0; i < (ll)heavy.size(); ++i) pre[i][a[u]] += freq[i];
	if ((ll)v1[a[u]].size() > block) ++freq[get_rank(a[u])];
	for (ll v : adj[u]) {
		if (v == p) continue;
		dfs(u,v);
	}
	if ((ll)v1[a[u]].size() > block) --freq[get_rank(a[u])];
	tout[u] = timer;
}

void solve() {
	cin >> n >> r >> q;
	cin >> a[1];
	v1[a[1]].push_back(1);
	for (int i = 2; i <= n; ++i) {
		ll y;
		cin >> y >> a[i];
		adj[i].push_back(y);
		adj[y].push_back(i);
		v1[a[i]].push_back(i);
	}
	for (int i = 1; i <= r; ++i) if ((ll)v1[i].size() > block) heavy.push_back(i);
	dfs(-1,1);
	for (int i = 1; i <= n; i++) v2[a[i]].push_back(tin[i]);
	for (int i = 1; i <= r; i++) sort(v2[i].begin(), v2[i].end());
	while (q--) {
		ll r1, r2;
		cin >> r1 >> r2;
		if ((ll)v1[r1].size() > block) cout << pre[get_rank(r1)][r2] << endl;
	 	else {
			ll ans = 0;
			for (ll i : v1[r1]) {
				ans += upper_bound(v2[r2].begin(), v2[r2].end(), tout[i]) -  lower_bound(v2[r2].begin(), v2[r2].end(), tin[i]);
			}
			cout << ans << endl;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	ll testCase = 1;
//	cin >> testCase;
	while (testCase--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:65:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:66:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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