Submission #733234

#	Time	Username	Problem	Language	Result	Execution time	Memory
733234		penguin133	Regions (IOI09_regions)	C++17	30 / 100	2632 ms	131072 KiB

regions

#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];
 
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;
}
 
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);
	}
	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 (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 15 / 85