Submission #935699

#	Time	Username	Problem	Language	Result	Execution time	Memory
935699		OAleksa	Regions (IOI09_regions)	C++14	80 / 100	8069 ms	113216 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int R = 25069;
const int K = 17;
const int B = 250;
int n, q, r, a[N], cnt[R];
int timer, tin[N], tout[N], up[N][K];
int st[R * K * 15], lc[R * K * 15], rc[R * K * 15];
int root[N], node, l[R];
map<pair<int, int>, int> was;
vector<int> g[N], clr[R];
void modify(int v, int v1, int tl, int tr, int pos) {
	if (tl == tr)
		st[v] = st[v1] + 1;
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid) {
			lc[v] = ++node;
			rc[v] = rc[v1];
			modify(lc[v], lc[v1], tl, mid, pos);
		}
		else {
			rc[v] = ++node;
			lc[v] = lc[v1];
			modify(rc[v], rc[v1], mid + 1, tr, pos);
		}
		st[v] = st[lc[v]] + st[rc[v]];
	}
}

int get(int v, int tl, int tr, int pos) {
	if (tl == tr)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid)
			return get(lc[v], tl, mid, pos);
		else
			return get(rc[v], mid + 1, tr, pos);
	}
}

bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)	
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	root[v] = ++node;
	clr[a[v]].push_back(v);
	modify(root[v], root[p], 1, n, a[v]);
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> r >> q;
  	cin >> a[1];
  	for (int i = 2;i <= n;i++) {
  		int x;
  		cin >> x >> a[i];
  		g[x].push_back(i);
  		g[i].push_back(x);
  		cnt[a[i]]++;
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= r;i++) {
			if (!clr[i].empty()) {
				l[i] = clr[i].front();
				for (int j = 1;j < (int)clr[i].size();j++)
					l[i] = lca(l[i], clr[i][j]);
			}
		}
  	while (q--) {
  		int r1, r2;
  		cin >> r1 >> r2;
  		int ans = 0;
  		if (was.count({r1, r2}))
  			ans = was[{r1, r2}];
  		else if (cnt[r1] > B && cnt[r2] > B) {
  			//nadji lca i samo dfs
  			if (!clr[r1].empty()) {
  				function<void(int, int, int, int, int)> dfs = [&](int v, int p, int r1, int r2, int c) {
  					if (a[v] == r2)
  						ans += c;
  					for (auto u : g[v]) {
  						if (u == p)
  							continue;
  						dfs(u, v, r1, r2, c + (a[v] == r1));
  					}
  				};
  				dfs(l[r1], up[l[r1]][0], r1, r2, 0);
  			}
  		}
  		else if (cnt[r1] <= B) {
  			//binarna
  			for (auto i : clr[r1]) {
  				int m = clr[r2].size();
	  			int l = 0, r = m - 1, L = -1;
	  			while (l <= r) {
	  				int mid = (l + r) / 2;
	  				if (tin[clr[r2][mid]] >= tin[i]) {
	  					L = mid;
	  					r = mid - 1;
	  				}
	  				else
	  					l = mid + 1;
	  			}
	  			l = 0, r = m - 1;
	  			int R = -1;
	  			while (l <= r) {
	  				int mid = (l + r) / 2;
	  				if (tin[clr[r2][mid]] <= tout[i]) {
	  					R = mid;
	  					l = mid + 1;
	  				}
	  				else
	  					r = mid - 1;
	  			}
	  			if (L != -1 && R != -1)
	  				ans += R - L + 1;
  			}
  		}
  		else {
  			for (auto i : clr[r2]) 
  				ans += get(root[i], 1, n, r1);
  		}
  		//nsqrtnlogn
  		cout << ans << endl;
  		if (!was.count({r1, r2}))
  			was[{r1, r2}] = ans;
  	}
  }
  return 0;
}

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