oj.uz

Submission #935712

# Submission time Handle Problem Language Result Execution time Memory
935712 2024-02-29T12:18:11 Z OAleksa Regions (IOI09_regions) C++14
0 / 100
 4925 ms 112848 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14936 KB Output isn't correct
2 Incorrect 2 ms 14936 KB Output isn't correct
3 Incorrect 4 ms 15268 KB Output isn't correct
4 Incorrect 4 ms 15032 KB Output isn't correct
5 Incorrect 5 ms 15308 KB Output isn't correct
6 Incorrect 10 ms 15740 KB Output isn't correct
7 Incorrect 18 ms 15912 KB Output isn't correct
8 Incorrect 19 ms 15736 KB Output isn't correct
9 Incorrect 28 ms 19444 KB Output isn't correct
10 Incorrect 52 ms 18576 KB Output isn't correct
11 Incorrect 59 ms 19524 KB Output isn't correct
12 Incorrect 70 ms 23144 KB Output isn't correct
13 Incorrect 73 ms 25684 KB Output isn't correct
14 Incorrect 86 ms 27372 KB Output isn't correct
15 Incorrect 104 ms 32472 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 584 ms 42420 KB Output isn't correct
2 Incorrect 778 ms 42704 KB Output isn't correct
3 Incorrect 809 ms 53632 KB Output isn't correct
4 Incorrect 156 ms 28928 KB Output isn't correct
5 Incorrect 209 ms 32724 KB Output isn't correct
6 Incorrect 346 ms 34024 KB Output isn't correct
7 Incorrect 522 ms 40392 KB Output isn't correct
8 Incorrect 521 ms 56048 KB Output isn't correct
9 Incorrect 879 ms 76288 KB Output isn't correct
10 Incorrect 1063 ms 86772 KB Output isn't correct
11 Incorrect 1262 ms 93048 KB Output isn't correct
12 Incorrect 644 ms 81780 KB Output isn't correct
13 Incorrect 777 ms 84532 KB Output isn't correct
14 Incorrect 4925 ms 90688 KB Output isn't correct
15 Incorrect 1275 ms 101532 KB Output isn't correct
16 Incorrect 1301 ms 104952 KB Output isn't correct
17 Incorrect 3229 ms 112848 KB Output isn't correct