oj.uz

Submission #935716

# Submission time Handle Problem Language Result Execution time Memory
935716 2024-02-29T12:20:28 Z OAleksa Regions (IOI09_regions) C++14
100 / 100
 5465 ms 112812 KB 
#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 = 600;
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}];
  			cout << ans << endl;
  			continue;
  		}
  		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;
  		was[{r1, r2}] = ans;
  	}
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 15012 KB Output is correct
4 Correct 5 ms 15020 KB Output is correct
5 Correct 6 ms 15564 KB Output is correct
6 Correct 12 ms 15648 KB Output is correct
7 Correct 16 ms 15728 KB Output is correct
8 Correct 18 ms 15792 KB Output is correct
9 Correct 34 ms 18360 KB Output is correct
10 Correct 61 ms 19336 KB Output is correct
11 Correct 75 ms 20028 KB Output is correct
12 Correct 94 ms 22880 KB Output is correct
13 Correct 128 ms 25392 KB Output is correct
14 Correct 172 ms 27432 KB Output is correct
15 Correct 205 ms 32516 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 42168 KB Output is correct
2 Correct 1095 ms 42864 KB Output is correct
3 Correct 1547 ms 53912 KB Output is correct
4 Correct 179 ms 27724 KB Output is correct
5 Correct 240 ms 32028 KB Output is correct
6 Correct 343 ms 34228 KB Output is correct
7 Correct 527 ms 40560 KB Output is correct
8 Correct 880 ms 56108 KB Output is correct
9 Correct 1593 ms 75476 KB Output is correct
10 Correct 3601 ms 87264 KB Output is correct
11 Correct 3190 ms 93628 KB Output is correct
12 Correct 1032 ms 81520 KB Output is correct
13 Correct 1606 ms 84400 KB Output is correct
14 Correct 5465 ms 90324 KB Output is correct
15 Correct 2584 ms 101228 KB Output is correct
16 Correct 2729 ms 104792 KB Output is correct
17 Correct 4587 ms 112812 KB Output is correct