Submission #517060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
517060	2022-01-22T13:04:40 Z	Yuisuyuno	Regions (IOI09_regions)	C++14	100 / 100	4387 ms	118504 KB

regions

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
bool vis[25001];
int n,r,q,cnt=1, a[maxn], st[maxn], en[maxn], B[maxn];
unordered_map<int,int> calc[25001];
vector<int> adj[maxn], v[25001];
void dfs(int s, int p = -1)
{
	st[s] = cnt++;
	for(auto u : adj[s])
		if(u!=p) dfs(u,s);
	en[s] = cnt-1;
}

int32_t main()
{
	cin >> n >> r >> q >> a[1];
	for(int i = 2; i <= n; i++)
	{
		int x; cin >> x >> a[i];
		adj[x].push_back(i);
	}
	int K = sqrt(n);
	dfs(1); for(int i = 1; i <= n; i++) B[st[i]]=i;
	for(int i = 1; i <= n; i++) v[a[B[i]]].push_back(st[B[i]]);
	for(int i = 1; i <= n; i++)
	{
		if(vis[a[B[i]]]) continue;
		if(v[a[B[i]]].size()<=K) continue;
		vis[a[B[i]]]=true;
		int pref[n+2]{0};
		for(auto u : v[a[B[i]]])
		{
			int l = st[B[u]], r = en[B[u]];
			pref[l]++, pref[r+1]--;
		}
		for(int j = 1; j <= n; j++)
			pref[j]+=pref[j-1], calc[a[B[j]]][a[B[i]]]+=pref[j];
	}
	while(q--)
	{
		int a, b, ans = 0; cin >> a >> b;
		if(v[a].size()<=K){
			for(auto u : v[a]){
				int l = st[B[u]], r = en[B[u]];
				auto itr = upper_bound(v[b].begin(), v[b].end(), r)-v[b].begin();
				auto itr2 = upper_bound(v[b].begin(), v[b].end(), l)-v[b].begin();
				if(itr) itr--, ans+=max((int)(itr-itr2)+1, 0);
			}
		}
		else ans = calc[b][a];
		cout << ans << endl;
	}
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:30:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |   if(v[a[B[i]]].size()<=K) continue;
      |      ~~~~~~~~~~~~~~~~~^~~
regions.cpp:44:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |   if(v[a].size()<=K){
      |      ~~~~~~~~~~~^~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6856 KB	Output is correct
2	Correct	3 ms	6856 KB	Output is correct
3	Correct	6 ms	6856 KB	Output is correct
4	Correct	6 ms	6928 KB	Output is correct
5	Correct	9 ms	6996 KB	Output is correct
6	Correct	20 ms	6984 KB	Output is correct
7	Correct	33 ms	6984 KB	Output is correct
8	Correct	41 ms	6984 KB	Output is correct
9	Correct	40 ms	7368 KB	Output is correct
10	Correct	87 ms	7368 KB	Output is correct
11	Correct	122 ms	7752 KB	Output is correct
12	Correct	148 ms	8136 KB	Output is correct
13	Correct	206 ms	7836 KB	Output is correct
14	Correct	249 ms	8548 KB	Output is correct
15	Correct	318 ms	10904 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1591 ms	11624 KB	Output is correct
2	Correct	1975 ms	10540 KB	Output is correct
3	Correct	2715 ms	13280 KB	Output is correct
4	Correct	269 ms	8460 KB	Output is correct
5	Correct	409 ms	10048 KB	Output is correct
6	Correct	752 ms	27408 KB	Output is correct
7	Correct	1386 ms	31084 KB	Output is correct
8	Correct	1728 ms	57024 KB	Output is correct
9	Correct	2267 ms	15724 KB	Output is correct
10	Correct	4387 ms	118504 KB	Output is correct
11	Correct	4033 ms	15424 KB	Output is correct
12	Correct	1349 ms	20212 KB	Output is correct
13	Correct	1752 ms	19728 KB	Output is correct
14	Correct	2696 ms	33600 KB	Output is correct
15	Correct	2906 ms	25452 KB	Output is correct
16	Correct	3100 ms	30868 KB	Output is correct
17	Correct	3497 ms	42324 KB	Output is correct