oj.uz

Submission #935714

# Submission time Handle Problem Language Result Execution time Memory
935714 2024-02-29T12:18:56 Z OAleksa Regions (IOI09_regions) C++14
95 / 100
 8000 ms 112652 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 = 500;
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 3 ms 14936 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 4 ms 15192 KB Output is correct
4 Correct 4 ms 15020 KB Output is correct
5 Correct 5 ms 15308 KB Output is correct
6 Correct 10 ms 15932 KB Output is correct
7 Correct 18 ms 15668 KB Output is correct
8 Correct 20 ms 15988 KB Output is correct
9 Correct 35 ms 18392 KB Output is correct
10 Correct 60 ms 19108 KB Output is correct
11 Correct 81 ms 19248 KB Output is correct
12 Correct 117 ms 22556 KB Output is correct
13 Correct 121 ms 25448 KB Output is correct
14 Correct 182 ms 27232 KB Output is correct
15 Correct 228 ms 33052 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 42436 KB Output is correct
2 Correct 1218 ms 43296 KB Output is correct
3 Correct 1601 ms 53952 KB Output is correct
4 Correct 177 ms 28192 KB Output is correct
5 Correct 314 ms 33012 KB Output is correct
6 Correct 424 ms 34672 KB Output is correct
7 Correct 537 ms 40252 KB Output is correct
8 Correct 790 ms 56416 KB Output is correct
9 Correct 1742 ms 76360 KB Output is correct
10 Correct 3804 ms 87024 KB Output is correct
11 Correct 3322 ms 93060 KB Output is correct
12 Correct 1140 ms 81740 KB Output is correct
13 Correct 1686 ms 84560 KB Output is correct
14 Execution timed out 8050 ms 89968 KB Time limit exceeded
15 Correct 2785 ms 101252 KB Output is correct
16 Correct 2786 ms 104932 KB Output is correct
17 Correct 5598 ms 112652 KB Output is correct