oj.uz

Submission #733251

# Submission time Handle Problem Language Result Execution time Memory
733251 2023-04-30T09:55:05 Z penguin133 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 88044 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> mp[200005];
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){
	mp[x][A[x]]++;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
		if(mp[i].size() > mp[x].size())swap(mp[x], mp[i]);
		for(auto [j, k] : mp[i])mp[x][j] += k;
	}
	if(big[A[x]] >= 500)for(auto [i, j] : mp[x])fin[A[x]][i] += j;
}
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:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16720 KB Output is correct
2 Correct 8 ms 16720 KB Output is correct
3 Correct 12 ms 16720 KB Output is correct
4 Correct 12 ms 16720 KB Output is correct
5 Correct 16 ms 16848 KB Output is correct
6 Correct 24 ms 16976 KB Output is correct
7 Correct 38 ms 17120 KB Output is correct
8 Correct 41 ms 17232 KB Output is correct
9 Correct 53 ms 18228 KB Output is correct
10 Correct 99 ms 19280 KB Output is correct
11 Correct 127 ms 20176 KB Output is correct
12 Correct 182 ms 20744 KB Output is correct
13 Correct 200 ms 22860 KB Output is correct
14 Correct 295 ms 24140 KB Output is correct
15 Correct 314 ms 28212 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1948 ms 31212 KB Output is correct
2 Correct 2017 ms 33356 KB Output is correct
3 Correct 2842 ms 35236 KB Output is correct
4 Correct 301 ms 24904 KB Output is correct
5 Correct 382 ms 26240 KB Output is correct
6 Correct 1677 ms 36804 KB Output is correct
7 Correct 1748 ms 36004 KB Output is correct
8 Correct 1617 ms 44000 KB Output is correct
9 Correct 2611 ms 52872 KB Output is correct
10 Correct 4510 ms 58028 KB Output is correct
11 Correct 4400 ms 74356 KB Output is correct
12 Correct 2588 ms 62676 KB Output is correct
13 Correct 5982 ms 63036 KB Output is correct
14 Correct 7116 ms 88044 KB Output is correct
15 Execution timed out 8100 ms 46508 KB Time limit exceeded
16 Execution timed out 8082 ms 66692 KB Time limit exceeded
17 Execution timed out 8036 ms 75232 KB Time limit exceeded