oj.uz

답안 #517060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
517060 2022-01-22T13:04:40 Z Yuisuyuno Regions (IOI09_regions) C++14
100 / 100
 4387 ms 118504 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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