oj.uz

Submission #408829

# Submission time Handle Problem Language Result Execution time Memory
408829 2021-05-19T17:30:21 Z vuhoanggiap Regions (IOI09_regions) C++17
100 / 100
 4230 ms 29820 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 7 ms 5576 KB Output is correct
5 Correct 12 ms 5576 KB Output is correct
6 Correct 33 ms 5576 KB Output is correct
7 Correct 44 ms 5576 KB Output is correct
8 Correct 52 ms 5576 KB Output is correct
9 Correct 39 ms 5960 KB Output is correct
10 Correct 119 ms 5960 KB Output is correct
11 Correct 153 ms 6216 KB Output is correct
12 Correct 166 ms 6600 KB Output is correct
13 Correct 239 ms 6356 KB Output is correct
14 Correct 340 ms 6852 KB Output is correct
15 Correct 416 ms 8512 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1510 ms 10024 KB Output is correct
2 Correct 1657 ms 8596 KB Output is correct
3 Correct 2688 ms 11968 KB Output is correct
4 Correct 375 ms 6984 KB Output is correct
5 Correct 405 ms 8136 KB Output is correct
6 Correct 1265 ms 7964 KB Output is correct
7 Correct 1616 ms 8980 KB Output is correct
8 Correct 1714 ms 12516 KB Output is correct
9 Correct 2800 ms 13488 KB Output is correct
10 Correct 4230 ms 16948 KB Output is correct
11 Correct 4211 ms 13536 KB Output is correct
12 Correct 1449 ms 15636 KB Output is correct
13 Correct 2392 ms 15956 KB Output is correct
14 Correct 2788 ms 18776 KB Output is correct
15 Correct 3816 ms 20764 KB Output is correct
16 Correct 3568 ms 28228 KB Output is correct
17 Correct 3332 ms 29820 KB Output is correct