oj.uz

Submission #935711

# Submission time Handle Problem Language Result Execution time Memory
935711 2024-02-29T12:17:15 Z OAleksa Regions (IOI09_regions) C++14
0 / 100
 8000 ms 112344 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, 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 2 ms 14936 KB Output isn't correct
2 Incorrect 2 ms 14936 KB Output isn't correct
3 Incorrect 3 ms 15272 KB Output isn't correct
4 Incorrect 4 ms 15280 KB Output isn't correct
5 Incorrect 7 ms 15828 KB Output isn't correct
6 Incorrect 11 ms 15684 KB Output isn't correct
7 Incorrect 19 ms 16732 KB Output isn't correct
8 Incorrect 18 ms 15760 KB Output isn't correct
9 Incorrect 32 ms 18640 KB Output isn't correct
10 Incorrect 37 ms 19260 KB Output isn't correct
11 Incorrect 56 ms 20380 KB Output isn't correct
12 Incorrect 80 ms 23180 KB Output isn't correct
13 Incorrect 77 ms 25116 KB Output isn't correct
14 Incorrect 101 ms 27320 KB Output isn't correct
15 Incorrect 101 ms 32332 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1091 ms 42456 KB Output isn't correct
2 Incorrect 720 ms 42904 KB Output isn't correct
3 Incorrect 852 ms 54256 KB Output isn't correct
4 Incorrect 155 ms 27892 KB Output isn't correct
5 Incorrect 229 ms 33184 KB Output isn't correct
6 Incorrect 426 ms 34568 KB Output isn't correct
7 Incorrect 545 ms 40892 KB Output isn't correct
8 Incorrect 536 ms 56472 KB Output isn't correct
9 Incorrect 931 ms 75964 KB Output isn't correct
10 Execution timed out 8064 ms 84908 KB Time limit exceeded
11 Incorrect 1263 ms 93828 KB Output isn't correct
12 Incorrect 667 ms 81084 KB Output isn't correct
13 Incorrect 807 ms 84524 KB Output isn't correct
14 Incorrect 5059 ms 90420 KB Output isn't correct
15 Incorrect 1228 ms 100508 KB Output isn't correct
16 Incorrect 1378 ms 104556 KB Output isn't correct
17 Incorrect 3291 ms 112344 KB Output isn't correct