oj.uz

Submission #661133

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

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

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()
{
	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 8784 KB Output is correct
2 Correct 5 ms 8784 KB Output is correct
3 Correct 6 ms 8912 KB Output is correct
4 Correct 8 ms 8912 KB Output is correct
5 Correct 13 ms 8912 KB Output is correct
6 Correct 24 ms 9424 KB Output is correct
7 Correct 36 ms 9168 KB Output is correct
8 Correct 41 ms 9296 KB Output is correct
9 Correct 53 ms 9936 KB Output is correct
10 Correct 86 ms 10192 KB Output is correct
11 Correct 140 ms 10144 KB Output is correct
12 Correct 154 ms 11080 KB Output is correct
13 Correct 203 ms 10464 KB Output is correct
14 Correct 339 ms 10740 KB Output is correct
15 Correct 415 ms 13988 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1793 ms 14008 KB Output is correct
2 Correct 1964 ms 12760 KB Output is correct
3 Correct 3159 ms 16328 KB Output is correct
4 Correct 371 ms 17668 KB Output is correct
5 Correct 513 ms 21548 KB Output is correct
6 Correct 793 ms 24380 KB Output is correct
7 Correct 1417 ms 30880 KB Output is correct
8 Correct 1458 ms 36808 KB Output is correct
9 Correct 2938 ms 45580 KB Output is correct
10 Incorrect 4581 ms 68180 KB Output isn't correct
11 Incorrect 5223 ms 61272 KB Output isn't correct
12 Correct 2248 ms 48280 KB Output is correct
13 Correct 2997 ms 48824 KB Output is correct
14 Correct 3297 ms 55652 KB Output is correct
15 Incorrect 4975 ms 68332 KB Output isn't correct
16 Incorrect 5581 ms 76036 KB Output isn't correct
17 Correct 4210 ms 66588 KB Output is correct