oj.uz

Submission #733257

# Submission time Handle Problem Language Result Execution time Memory
733257 2023-04-30T09:59:59 Z penguin133 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 78520 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]] >= 1000)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] >= 1000){
				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 11 ms 16720 KB Output is correct
2 Correct 17 ms 16724 KB Output is correct
3 Correct 12 ms 16720 KB Output is correct
4 Correct 11 ms 16720 KB Output is correct
5 Correct 32 ms 16848 KB Output is correct
6 Correct 25 ms 16976 KB Output is correct
7 Correct 43 ms 17144 KB Output is correct
8 Correct 41 ms 17232 KB Output is correct
9 Correct 40 ms 18128 KB Output is correct
10 Correct 111 ms 19280 KB Output is correct
11 Correct 246 ms 20172 KB Output is correct
12 Correct 214 ms 20792 KB Output is correct
13 Correct 232 ms 22864 KB Output is correct
14 Correct 368 ms 24016 KB Output is correct
15 Correct 351 ms 28212 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2995 ms 31116 KB Output is correct
2 Correct 3094 ms 33288 KB Output is correct
3 Correct 4119 ms 35228 KB Output is correct
4 Correct 261 ms 24812 KB Output is correct
5 Correct 472 ms 26148 KB Output is correct
6 Correct 1568 ms 29644 KB Output is correct
7 Correct 2383 ms 35908 KB Output is correct
8 Correct 1734 ms 42008 KB Output is correct
9 Correct 3690 ms 52876 KB Output is correct
10 Correct 5336 ms 58084 KB Output is correct
11 Correct 4203 ms 74328 KB Output is correct
12 Correct 2456 ms 62704 KB Output is correct
13 Correct 5624 ms 63028 KB Output is correct
14 Correct 5963 ms 78520 KB Output is correct
15 Execution timed out 8073 ms 46552 KB Time limit exceeded
16 Execution timed out 8010 ms 66400 KB Time limit exceeded
17 Execution timed out 8101 ms 69776 KB Time limit exceeded