oj.uz

Submission #733246

# Submission time Handle Problem Language Result Execution time Memory
733246 2023-04-30T09:46:23 Z penguin133 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 40724 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];
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;
	}
	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);
	}
	if(r > 500){
		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;
			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:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main(){
      | ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16720 KB Output is correct
2 Correct 10 ms 16744 KB Output is correct
3 Correct 11 ms 16720 KB Output is correct
4 Correct 14 ms 16720 KB Output is correct
5 Correct 18 ms 16936 KB Output is correct
6 Correct 39 ms 20092 KB Output is correct
7 Correct 44 ms 18040 KB Output is correct
8 Correct 51 ms 19156 KB Output is correct
9 Correct 139 ms 23556 KB Output is correct
10 Correct 153 ms 26768 KB Output is correct
11 Correct 169 ms 24108 KB Output is correct
12 Correct 504 ms 32536 KB Output is correct
13 Correct 181 ms 26808 KB Output is correct
14 Correct 207 ms 25184 KB Output is correct
15 Correct 642 ms 30076 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1182 ms 30616 KB Output is correct
2 Correct 1084 ms 33092 KB Output is correct
3 Correct 2269 ms 36016 KB Output is correct
4 Correct 310 ms 19172 KB Output is correct
5 Correct 382 ms 20808 KB Output is correct
6 Correct 1236 ms 20784 KB Output is correct
7 Correct 1838 ms 22352 KB Output is correct
8 Correct 1177 ms 27668 KB Output is correct
9 Correct 2311 ms 29888 KB Output is correct
10 Correct 4228 ms 34476 KB Output is correct
11 Correct 4608 ms 30800 KB Output is correct
12 Correct 6036 ms 31504 KB Output is correct
13 Correct 6690 ms 31772 KB Output is correct
14 Execution timed out 8021 ms 31712 KB Time limit exceeded
15 Execution timed out 8041 ms 35664 KB Time limit exceeded
16 Correct 7428 ms 40724 KB Output is correct
17 Execution timed out 8048 ms 40276 KB Time limit exceeded