Submission #655596

#	Time	Username	Problem	Language	Result	Execution time	Memory
655596		rafatoa	Regions (IOI09_regions)	C++17	30 / 100	2946 ms	131072 KiB

regions

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#pragma GCC optimize ("Ofast")

#define double ld

#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define rs resize
#define as assign
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define MP make_pair

#define int long long
const int inf = 2e9;
const int INF = 4e18;

void solve(){
	int n, r, q; cin >> n >> r >> q;
	vvi adj(n+1);
	vi h(n+1);

	cin >> h[1];
	for(int i=2; i<=n; i++){
		int x; cin >> x; cin >> h[i];
		adj[x].pb(i); adj[i].pb(x);
	}

	map<pi, int> ans;
	unordered_map<int, int> mp;

	function<void(int, int)> dfs = [&](int s, int e){
		for(auto &[el, times]:mp)
			ans[{h[s], el}] += times;
		
		mp[h[s]]++;
		for(auto u:adj[s])
			if(u != e) dfs(u, s);
		
		mp[h[s]]--;
		if(mp[h[s]] == 0) mp.erase(h[s]);
	};
	dfs(1, 0);

	while(q--){
		int r1, r2; cin >> r1 >> r2;
		cout << ans[{r2, r1}] << endl;
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	// #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
	
    solve();
    return 0;
}

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