Submission #666427

#	Time	Username	Problem	Language	Result	Execution time	Memory
666427		Melika0gh	Regions (IOI09_regions)	C++17	100 / 100	5480 ms	82528 KiB

regions

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10, maxr = 25e3 + 10, maxsq = 500;
int st[maxn], ft[maxn], pnt[maxn], cnt_big[maxsq + 10], cnt[maxsq + 10][maxr], h[maxn];
vector<int> tmp_team[maxr], team[maxr];
vector<int> adj[maxn];
int n, q, r, t;

void Dfs(int v, int p)
{
	st[v] = t++;
	if(pnt[h[v]] > 0)
		cnt_big[pnt[h[v]]]++;
	
	team[h[v]].push_back(st[v]);
	
	for(int u : adj[v])
	{
		for(int i = 1; i < maxsq + 10; i++)
			cnt[i][h[u]] += cnt_big[i];
			
		Dfs(u, v);
	}
	
	if(pnt[h[v]] > 0)
		cnt_big[pnt[h[v]]]--;
		
	ft[v] = t;
}

int Bs(int l, int r, int tim, int x) // (l, r]
{
	if(r - l <= 1)
		return r;
	
	int mid = (r + l) / 2;
	if(team[tim][mid] < x)
		return Bs(mid, r, tim, x);
	else
		return Bs(l, mid, tim, x);
}

int main()
{
	cin >> n >> r >> q;
	cin >> h[0];
	tmp_team[h[0]].push_back(0);
	for(int i = 1; i < n; i++)
	{
		int p;
		cin >> p >> h[i];
		tmp_team[h[i]].push_back(i);
		p--;
		adj[p].push_back(i);
	}
	for(int i = 1; i <= r; i++)
	{
		if(tmp_team[i].size() > maxsq)
			pnt[i] = ++t;
	}
	t = 0;
	Dfs(0, -1);
	
	for(q; q > 0; q--)
	{
		int r1, r2;
		cin >> r1 >> r2;
		if(pnt[r1] > 0)
		{
			cout << cnt[pnt[r1]][r2] << endl;
			continue;
		}
		int ans = 0;
		for(int v : tmp_team[r1])
		{
			int l = Bs(-1, team[r2].size(), r2, st[v]);
			int r = Bs(-1, team[r2].size(), r2, ft[v]);
			if(r >= l)
				ans += r - l;
		}
		cout << ans << endl;
	}
	
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:65:6: warning: statement has no effect [-Wunused-value]
   65 |  for(q; q > 0; q--)
      |      ^

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