oj.uz

Submission #661136

# Submission time Handle Problem Language Result Execution time Memory
661136 2022-11-24T15:43:12 Z parsadox2 Regions (IOI09_regions) C++14
100 / 100
 5341 ms 80244 KB 
#include <bits/stdc++.h>
#define pb push_back
#define debug(x)  cout << #x << " = " << x << ", "
using namespace std;

const int maxn = 2e5 + 10 , maxsq = 500 , maxr = 25e3 + 10;

int n , r , q , col[maxn] , ps[maxn] , tim , cnt[maxn] , ans[maxsq + 10][maxr] , st[maxn] , fn[maxn];
vector <int> g[maxn] , all[maxr] , allst[maxr];

void dfs(int v , int p = -1)
{
	st[v] = tim;
	allst[col[v]].pb(tim);
	tim++;
	if(ps[col[v]] != -1)
		cnt[ps[col[v]]]++;
	for(auto u : g[v])   if(u != p)
	{
		for(int i = 0 ; i < maxsq + 10 ; i++)
			ans[i][col[u]] += cnt[i];
		dfs(u , v);
	}
	if(ps[col[v]] != -1)
		cnt[ps[col[v]]]--;
	fn[v] = tim;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> r >> q;
	cin >> col[0];
	all[col[0]].pb(0);
	memset(ps , -1 , sizeof ps);
	for(int i =  1 ; i < n ; i++)
	{
		int p;
		cin >> p >> col[i];   p--;
		g[p].pb(i);
		all[col[i]].pb(i);
	}
	for(int i = 1 ; i <= r ; i++)   if(all[i].size() > maxsq)
	{
		ps[i] = tim;
		tim++;
	}
	tim = 0;
	dfs(tim);
	while(q--)
	{
		int a , b;
		cin >> a >> b;
		if(ps[a] != -1)
		{
			cout << ans[ps[a]][b] << endl;
			continue;
		}
		int res = 0;
		for(auto u : all[a])
		{
			int l , r;
			int low = -1 , high = allst[b].size();
			while(high - low > 1)
			{
				int mid = (high + low) / 2;
				if(allst[b][mid] >= st[u])
					high = mid;
				else
					low = mid;
			}
			l = high;
			low = -1;  high = allst[b].size();
			while(high - low > 1)
			{
				int mid = (high + low) / 2;
				if(allst[b][mid] < fn[u])
					low = mid;
				else
					high = mid;
			}
			r= high;
			res += (r - l);
		}
		cout << res << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9040 KB Output is correct
2 Correct 6 ms 9040 KB Output is correct
3 Correct 6 ms 9168 KB Output is correct
4 Correct 10 ms 9168 KB Output is correct
5 Correct 15 ms 9200 KB Output is correct
6 Correct 24 ms 9680 KB Output is correct
7 Correct 27 ms 9424 KB Output is correct
8 Correct 31 ms 9552 KB Output is correct
9 Correct 29 ms 10272 KB Output is correct
10 Correct 84 ms 10520 KB Output is correct
11 Correct 142 ms 10508 KB Output is correct
12 Correct 151 ms 11416 KB Output is correct
13 Correct 214 ms 10704 KB Output is correct
14 Correct 296 ms 11084 KB Output is correct
15 Correct 399 ms 14280 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1789 ms 14388 KB Output is correct
2 Correct 1942 ms 13064 KB Output is correct
3 Correct 2847 ms 16584 KB Output is correct
4 Correct 377 ms 18704 KB Output is correct
5 Correct 481 ms 22636 KB Output is correct
6 Correct 1378 ms 26048 KB Output is correct
7 Correct 1811 ms 33084 KB Output is correct
8 Correct 2087 ms 39016 KB Output is correct
9 Correct 2800 ms 48712 KB Output is correct
10 Correct 5341 ms 72612 KB Output is correct
11 Correct 5334 ms 66288 KB Output is correct
12 Correct 1975 ms 51712 KB Output is correct
13 Correct 2853 ms 52228 KB Output is correct
14 Correct 2602 ms 59804 KB Output is correct
15 Correct 3937 ms 73100 KB Output is correct
16 Correct 4262 ms 80244 KB Output is correct
17 Correct 3925 ms 70736 KB Output is correct