Submission #598516

#	Time	Username	Problem	Language	Result	Execution time	Memory
598516		l_reho	Regions (IOI09_regions)	C++14	1 / 100	1576 ms	131072 KiB

regions

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int N, R, Q, root;
vector<vector<int>> graph;
vector<map<int, int>> M;
vector<vector<int>> occ;
vector<int> region;


void precompute(int curr){
	
	vector<int> adj = graph[curr];
	
	M[curr][region[curr]]++;
	
	for(int a : adj){
		precompute(a);
		
		// bisogna fondere vector[a] in vector[curr]
		for(auto m : M[a])
			M[curr][m.first]+=m.second;
	}
	
	
}


void solve(){
	cin>>N>>R>>Q>>root;
	
	graph.assign(N+1, vector<int>());
	region.assign(N+1, 0);
	occ.assign(R+1, vector<int>());
	M.assign(N+1, map<int, int>());
	
	region[root] = root;
	occ[root].push_back(root);
	for(int i = 0; i < N-1; i++){
		int a, b;
		cin>>a>>b;
		
		graph[a].push_back(i+2);
		occ[b].push_back(i+2);
		region[i+2] = b;
	}
	
	precompute(root);
	
	int ans = 0;
	
	for(int i = 0; i < Q; i++){
		int r1, r2;
		cin>>r1>>r2;
		ans = 0;
		vector<int> o = occ[r1];
		
		for(int e : o) ans += M[e][r2];
		
		cout<<ans<<endl;
	}
	
}

int main(){
	solve();
	
	return 0;
}

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