Submission #935240

#	Time	Username	Problem	Language	Result	Execution time	Memory
935240		OAleksa	Regions (IOI09_regions)	C++14	13 / 100	8100 ms	49332 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 = 450;
int n, q, r, a[N], cnt[R], st[K * N], lc[K * N], rc[K * N], root[N];
int timer, tin[N], tout[N], up[N][K];
map<pair<int, int>, int> was;
vector<int> g[N], clr[R];
void modify(int v, int tl, int tr, int pos, int x) {
	if (tl == tr)
		st[v] += x;
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid)
			modify(v * 2, tl, mid, pos, x);
		else
			modify(v * 2 + 1, mid + 1, tr, pos, x);
		st[v] = st[v * 2] + st[v * 2 + 1];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return get(v * 2, tl, mid, l, r) + get(v * 2 + 1, mid + 1, tr, l, r);
	}
}
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;
	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];
  	clr[a[1]].push_back(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]]++;
  		clr[a[i]].push_back(i);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= r;i++) {
			sort(clr[i].begin(), clr[i].end(), [&](int x, int y) {
				pair<int, int> f = {tin[x], tout[x]};
				pair<int, int> s = {tin[y], tout[y]};
				return f < s;	
			});
  	}
  	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()) {
  				int lc = clr[r1].front();
  				for (int i = 1;i < (int)clr[r1].size();i++)
  					lc = lca(lc, clr[r1][i]);
  				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(lc, up[lc][0], r1, r2, 0);
  			}
  		}
  		else if (cnt[r1] <= B) {
  			//pokreni dfs iz svakog
  			for (auto i : clr[r1]) {
  				function<void(int, int)> dfs = [&](int v, int p) {
  					ans += (a[v] == r2);
  					for (auto u : g[v]) {
  						if (u == p)
  							continue;
  						dfs(u, v);
  					}
  				};
  				dfs(i, up[i][0]);
  			}
  		}
  		else {
  			//offline kveriz
  			//[l, r] 
  			vector<pair<int, int>> kv;
  			for (auto i : clr[r2]) 
  				kv.push_back({tin[i], tout[i]});
  			sort(kv.begin(), kv.end());
  			int ptr = 0, m = clr[r1].size();
  			for (auto i : kv) {
  				int l, r;
  				tie(l, r) = i;
  				while (ptr < m && tin[clr[r1][ptr]] < l) {
  					modify(1, 1, n, tout[clr[r1][ptr]], 1);
  					ptr++;
  				}
  				ans += get(1, 1, n, r, n);
  			}
  		}
  		//nsqrtnlogn
  		cout << ans << endl;
  		if (!was.count({r1, r2}))
  			was[{r1, r2}] = ans;
  	}
  }
  return 0;
}

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