oj.uz

Submission #661135

# Submission time Handle Problem Language Result Execution time Memory
661135 2022-11-24T15:41:10 Z parsadox2 Regions (IOI09_regions) C++14
80 / 100
 4918 ms 76060 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()
{
	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 4 ms 8912 KB Output is correct
2 Correct 5 ms 8912 KB Output is correct
3 Correct 7 ms 8912 KB Output is correct
4 Correct 10 ms 8912 KB Output is correct
5 Correct 12 ms 9012 KB Output is correct
6 Correct 19 ms 9424 KB Output is correct
7 Correct 25 ms 9252 KB Output is correct
8 Correct 25 ms 9296 KB Output is correct
9 Correct 41 ms 9936 KB Output is correct
10 Correct 84 ms 10192 KB Output is correct
11 Correct 131 ms 10192 KB Output is correct
12 Correct 120 ms 11124 KB Output is correct
13 Correct 188 ms 10452 KB Output is correct
14 Correct 294 ms 10792 KB Output is correct
15 Correct 275 ms 14012 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1740 ms 14140 KB Output is correct
2 Correct 1745 ms 12812 KB Output is correct
3 Correct 2796 ms 16308 KB Output is correct
4 Correct 317 ms 17784 KB Output is correct
5 Correct 507 ms 21448 KB Output is correct
6 Correct 597 ms 24392 KB Output is correct
7 Correct 1474 ms 30824 KB Output is correct
8 Correct 1375 ms 37016 KB Output is correct
9 Correct 2886 ms 45512 KB Output is correct
10 Incorrect 4127 ms 68284 KB Output isn't correct
11 Incorrect 4918 ms 61380 KB Output isn't correct
12 Correct 2037 ms 48508 KB Output is correct
13 Correct 2510 ms 48828 KB Output is correct
14 Correct 2737 ms 55680 KB Output is correct
15 Incorrect 3964 ms 68204 KB Output isn't correct
16 Incorrect 4614 ms 76060 KB Output isn't correct
17 Correct 3859 ms 66508 KB Output is correct