oj.uz

Submission #666427

# Submission time Handle Problem Language Result Execution time Memory
666427 2022-11-28T15:44:10 Z Melika0gh Regions (IOI09_regions) C++17
100 / 100
 5480 ms 82528 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8272 KB Output is correct
2 Correct 5 ms 8272 KB Output is correct
3 Correct 6 ms 8264 KB Output is correct
4 Correct 8 ms 8272 KB Output is correct
5 Correct 12 ms 8400 KB Output is correct
6 Correct 20 ms 8912 KB Output is correct
7 Correct 29 ms 8688 KB Output is correct
8 Correct 40 ms 8784 KB Output is correct
9 Correct 52 ms 9552 KB Output is correct
10 Correct 65 ms 9636 KB Output is correct
11 Correct 133 ms 9684 KB Output is correct
12 Correct 181 ms 10620 KB Output is correct
13 Correct 165 ms 9936 KB Output is correct
14 Correct 285 ms 10312 KB Output is correct
15 Correct 368 ms 14116 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1446 ms 13780 KB Output is correct
2 Correct 1847 ms 12232 KB Output is correct
3 Correct 2466 ms 16344 KB Output is correct
4 Correct 433 ms 17956 KB Output is correct
5 Correct 589 ms 22416 KB Output is correct
6 Correct 1395 ms 25176 KB Output is correct
7 Correct 1687 ms 32300 KB Output is correct
8 Correct 2056 ms 39180 KB Output is correct
9 Correct 2869 ms 48148 KB Output is correct
10 Correct 5079 ms 73060 KB Output is correct
11 Correct 5480 ms 65324 KB Output is correct
12 Correct 2425 ms 50964 KB Output is correct
13 Correct 2936 ms 51724 KB Output is correct
14 Correct 3191 ms 59112 KB Output is correct
15 Correct 4435 ms 73484 KB Output is correct
16 Correct 4258 ms 82528 KB Output is correct
17 Correct 4231 ms 72392 KB Output is correct