oj.uz

Submission #666426

# Submission time Handle Problem Language Result Execution time Memory
666426 2022-11-28T15:41:57 Z Melika0gh Regions (IOI09_regions) C++17
80 / 100
 4157 ms 72516 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10, maxr = 25e3, 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 4 ms 8272 KB Output is correct
3 Correct 6 ms 8272 KB Output is correct
4 Correct 7 ms 8272 KB Output is correct
5 Correct 10 ms 8400 KB Output is correct
6 Correct 26 ms 8912 KB Output is correct
7 Correct 34 ms 8648 KB Output is correct
8 Correct 34 ms 8784 KB Output is correct
9 Correct 55 ms 9500 KB Output is correct
10 Correct 86 ms 9584 KB Output is correct
11 Correct 132 ms 9696 KB Output is correct
12 Correct 172 ms 10636 KB Output is correct
13 Correct 166 ms 9948 KB Output is correct
14 Correct 276 ms 10320 KB Output is correct
15 Correct 384 ms 14152 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1709 ms 13796 KB Output is correct
2 Correct 1752 ms 12232 KB Output is correct
3 Correct 2591 ms 16292 KB Output is correct
4 Correct 428 ms 18100 KB Output is correct
5 Correct 518 ms 22312 KB Output is correct
6 Correct 1431 ms 25248 KB Output is correct
7 Correct 1974 ms 32216 KB Output is correct
8 Correct 1876 ms 39228 KB Output is correct
9 Correct 3028 ms 48080 KB Output is correct
10 Runtime error 16 ms 13288 KB Execution killed with signal 11
11 Runtime error 47 ms 16428 KB Execution killed with signal 11
12 Correct 2218 ms 50876 KB Output is correct
13 Correct 2837 ms 51476 KB Output is correct
14 Correct 3092 ms 59072 KB Output is correct
15 Runtime error 76 ms 20040 KB Execution killed with signal 11
16 Runtime error 102 ms 24660 KB Execution killed with signal 11
17 Correct 4157 ms 72516 KB Output is correct