oj.uz

Submission #733414

# Submission time Handle Problem Language Result Execution time Memory
733414 2023-04-30T16:41:23 Z penguin133 Regions (IOI09_regions) C++17
100 / 100
 4901 ms 66324 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, r, q;
map <int, int> cur;
vector <int> adj[200005];
int A[200005];
map <int, int> fin[25005];
int S[200005], E[200005];
const int sz = 500;
int big[25005];
vector <int> stuf[25005], stuf2[25005];
void dfs(int x, int par){
	if(big[A[x]] >= 500)cur[A[x]]++;
	for(auto [i, j] : cur)fin[i][A[x]] += j;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
	}
	if(big[A[x]] >= 500)cur[A[x]]--;
}
int cnt = 1;
void dfs2(int x, int par){
	S[x] = cnt++;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs2(i, x);
	}
	E[x] = cnt - 1;
}

int find(int idx, int l, int r){
	return upper_bound(stuf2[idx].begin(), stuf2[idx].end(), r) - lower_bound(stuf2[idx].begin(), stuf2[idx].end(), l);
}

void solve(){
	cin >> n >> r >> q;
	cin >> A[1];
	for(int i=2;i<=n;i++){
		int x; cin >> x >> A[i];
		adj[x].push_back(i);
		big[A[i]]++;
	}
	if(1){
		dfs(1, -1);
		dfs2(1, -1);
		for(int i=1;i<=n;i++)stuf[A[i]].push_back(i), stuf2[A[i]].push_back(S[i]);
		for(int i=1;i<=r;i++)sort(stuf2[i].begin(), stuf2[i].end());
		int ans =0 ;
		while(q--){
			ans = 0;
			int x, y; cin >> x >> y;
			if(big[x] >= 500){
				cout << fin[x][y] << endl;
				continue;
			}
			for(auto i : stuf[x]){
				ans += find(y, S[i], E[i]);
			}
			cout << ans << endl;
		}
		return;
	}
	dfs(1, -1);
	while(q--){
		int x, y; cin >> x >> y;
		cout << fin[x][y] << endl;
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

regions.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 4 ms 7376 KB Output is correct
3 Correct 6 ms 7376 KB Output is correct
4 Correct 7 ms 7376 KB Output is correct
5 Correct 11 ms 7376 KB Output is correct
6 Correct 19 ms 7504 KB Output is correct
7 Correct 47 ms 7504 KB Output is correct
8 Correct 41 ms 7504 KB Output is correct
9 Correct 51 ms 8272 KB Output is correct
10 Correct 89 ms 8120 KB Output is correct
11 Correct 140 ms 8576 KB Output is correct
12 Correct 116 ms 9424 KB Output is correct
13 Correct 116 ms 9040 KB Output is correct
14 Correct 282 ms 9828 KB Output is correct
15 Correct 284 ms 15048 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1839 ms 14836 KB Output is correct
2 Correct 1994 ms 13144 KB Output is correct
3 Correct 2697 ms 18224 KB Output is correct
4 Correct 240 ms 9872 KB Output is correct
5 Correct 355 ms 12988 KB Output is correct
6 Correct 1309 ms 19008 KB Output is correct
7 Correct 1834 ms 13340 KB Output is correct
8 Correct 1435 ms 24512 KB Output is correct
9 Correct 2238 ms 21776 KB Output is correct
10 Correct 4744 ms 30812 KB Output is correct
11 Correct 4901 ms 21772 KB Output is correct
12 Correct 1739 ms 24216 KB Output is correct
13 Correct 2260 ms 25460 KB Output is correct
14 Correct 2607 ms 46600 KB Output is correct
15 Correct 3399 ms 33992 KB Output is correct
16 Correct 3675 ms 46628 KB Output is correct
17 Correct 3797 ms 66324 KB Output is correct