oj.uz

Submission #935687

# Submission time Handle Problem Language Result Execution time Memory
935687 2024-02-29T11:35:49 Z OAleksa Regions (IOI09_regions) C++14
75 / 100
 8000 ms 106948 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 = 450;
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 = m;
	  			// 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 = m - 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;
	  			// }
	  			// ans += max(0, R - L + 1);
	  			for (int j = 0;j < m;j++) {
	  				ans += (tin[i] <= tin[clr[r2][j]] && tin[clr[r2][j]] <= tout[i]);
  					if (tin[clr[r2][j]] > tout[i])
  						break;
  				}
  			}
  		}
  		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 3 ms 14936 KB Output is correct
2 Correct 4 ms 14936 KB Output is correct
3 Correct 4 ms 15000 KB Output is correct
4 Correct 6 ms 15268 KB Output is correct
5 Correct 7 ms 15296 KB Output is correct
6 Correct 11 ms 15888 KB Output is correct
7 Correct 16 ms 15952 KB Output is correct
8 Correct 19 ms 16496 KB Output is correct
9 Correct 30 ms 18836 KB Output is correct
10 Correct 52 ms 19540 KB Output is correct
11 Correct 76 ms 20324 KB Output is correct
12 Correct 92 ms 22732 KB Output is correct
13 Correct 127 ms 23176 KB Output is correct
14 Correct 255 ms 24932 KB Output is correct
15 Correct 625 ms 32376 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2329 ms 42196 KB Output is correct
2 Correct 2207 ms 42816 KB Output is correct
3 Correct 3701 ms 53980 KB Output is correct
4 Correct 180 ms 26768 KB Output is correct
5 Correct 305 ms 32384 KB Output is correct
6 Correct 433 ms 34944 KB Output is correct
7 Correct 553 ms 40572 KB Output is correct
8 Correct 1482 ms 55416 KB Output is correct
9 Correct 1930 ms 76016 KB Output is correct
10 Execution timed out 8074 ms 85252 KB Time limit exceeded
11 Correct 5365 ms 93396 KB Output is correct
12 Correct 3970 ms 81732 KB Output is correct
13 Correct 5240 ms 84388 KB Output is correct
14 Execution timed out 8034 ms 86316 KB Time limit exceeded
15 Execution timed out 8089 ms 98884 KB Time limit exceeded
16 Execution timed out 8071 ms 96484 KB Time limit exceeded
17 Execution timed out 8086 ms 106948 KB Time limit exceeded