Submission #408829

#	Time	Username	Problem	Language	Result	Execution time	Memory
408829		vuhoanggiap	Regions (IOI09_regions)	C++17	100 / 100	4230 ms	29820 KiB

regions

#include <bits/stdc++.h>
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;

const int maxN = 2e5 + 5, maxR = 25005; 
const int blocksize = 500; 
int n, regions, q; 

vector<int> adj[maxN], R[maxR]; 
int id[maxN]; 
int euler; 
int s[maxN], e[maxN]; 

void dfs(int u) {
	s[u] = ++euler; 
	for(auto v : adj[u])
		dfs(v); 
	e[u] = euler; 
}

int idxLarge[maxN]; 
vector<int> large;  
vector<vector<int> > subLarge, ancLarge;

int dfsSubtree(int u, int reg) {
	int subtree = (id[u] == reg); 
	for(auto v : adj[u]) 
		subtree += dfsSubtree(v, reg); 
	subLarge[idxLarge[reg]][id[u]] += subtree; 
	return subtree; 
}

void dfsAncestor(int u, int reg, int cnt = 0) {
	cnt += (id[u] == reg); 
	ancLarge[idxLarge[reg]][id[u]] += cnt; 
	for(auto v : adj[u])
		dfsAncestor(v, reg, cnt); 
}

void solvelarge() {
	subLarge.resize((int)large.size() + 1, vector<int>(regions, 0)); 
	ancLarge.resize((int)large.size() + 1, vector<int>(regions, 0)); 
	for(int i = 1; i <= (int)large.size(); i++) {
		int reg = large[i - 1]; 
		idxLarge[reg] = i; 
		dfsSubtree(1, reg);
		dfsAncestor(1, reg);  
	}
}

inline bool cmp(const int &u, const int &v) {
	return s[u] < s[v]; 
}

inline bool isanc(const int &u, const int &v) {
	return s[u] <= s[v] && e[v] <= e[u]; 
}

int solve(int r1, int r2) {
	int ret = 0; 
	int p1 = 0, p2 = 0; 
	vector<int> vert, anc; 
	while(p1 < (int)R[r1].size() && p2 < (int)R[r2].size()) {
		if(cmp(R[r1][p1], R[r2][p2])) vert.pb(R[r1][p1++]); 
		else vert.pb(R[r2][p2++]); 
	}
	while(p1 < (int)R[r1].size()) vert.pb(R[r1][p1++]); 
	while(p2 < (int)R[r2].size()) vert.pb(R[r2][p2++]); 
	assert(is_sorted(all(vert), cmp)); 
	for(auto u : vert) {
		while(!anc.empty() && !isanc(anc.back(), u)) anc.pop_back(); 
		if(id[u] == r1) anc.pb(u); 
		else ret += (int)anc.size(); 
 	}
 	return ret; 
}

signed main() {
	cin >> n >> regions >> q; 
	for(int i = 1; i <= n; i++) {
		if(i == 1) cin >> id[i], R[id[i]].pb(i); 
		else {
			int par; cin >> par >> id[i];  
			adj[par].pb(i); 
			R[id[i]].pb(i); 
		}
	}
	dfs(1); 
	for(int reg = 1; reg <= regions; reg++) 
		sort(all(R[reg]), cmp);
	for(int reg = 1; reg <= regions; reg++) {
		if((int)R[reg].size() > blocksize) {
			large.pb(reg); 
		} 
	}
	solvelarge();
	for(int i = 1; i <= q; i++) {
		int reg1, reg2; cin >> reg1 >> reg2; 
		if(R[reg1].size() > blocksize) {
			cout << ancLarge[idxLarge[reg1]][reg2] << endl; 
		}
		else if(R[reg2].size() > blocksize) {
			cout << subLarge[idxLarge[reg2]][reg1] << endl; 
		}
		else {
			cout << solve(reg1, reg2) << endl; 
		}
	}
}

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