oj.uz

Submission #935689

# Submission time Handle Problem Language Result Execution time Memory
935689 2024-02-29T11:42:07 Z OAleksa Regions (IOI09_regions) C++14
90 / 100
 8000 ms 113108 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 = 300;
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;
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;
	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];
  	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) {
				return tin[x] < tin[y];
			});
		}
  	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) {
  			//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.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 4 ms 15008 KB Output is correct
4 Correct 4 ms 15016 KB Output is correct
5 Correct 6 ms 15716 KB Output is correct
6 Correct 16 ms 15360 KB Output is correct
7 Correct 18 ms 15952 KB Output is correct
8 Correct 19 ms 16264 KB Output is correct
9 Correct 36 ms 18888 KB Output is correct
10 Correct 50 ms 18696 KB Output is correct
11 Correct 77 ms 20092 KB Output is correct
12 Correct 102 ms 22760 KB Output is correct
13 Correct 120 ms 23496 KB Output is correct
14 Correct 176 ms 25540 KB Output is correct
15 Correct 201 ms 32096 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1676 ms 42004 KB Output is correct
2 Correct 1279 ms 43180 KB Output is correct
3 Correct 1576 ms 53504 KB Output is correct
4 Correct 179 ms 26740 KB Output is correct
5 Correct 238 ms 32544 KB Output is correct
6 Correct 520 ms 34560 KB Output is correct
7 Correct 514 ms 40904 KB Output is correct
8 Correct 1110 ms 55432 KB Output is correct
9 Correct 1820 ms 76072 KB Output is correct
10 Execution timed out 8060 ms 84324 KB Time limit exceeded
11 Correct 3342 ms 93456 KB Output is correct
12 Correct 1261 ms 81488 KB Output is correct
13 Correct 1647 ms 84224 KB Output is correct
14 Execution timed out 8029 ms 89048 KB Time limit exceeded
15 Correct 2814 ms 101040 KB Output is correct
16 Correct 2709 ms 102152 KB Output is correct
17 Correct 6636 ms 113108 KB Output is correct