oj.uz

Submission #935695

# Submission time Handle Problem Language Result Execution time Memory
935695 2024-02-29T11:51:48 Z OAleksa Regions (IOI09_regions) C++14
0 / 100
 198 ms 91588 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}];
  		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 << '\n';
  		if (!was.count({r1, r2}))
  			was[{r1, r2}] = ans;
  	}
  }
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 14936 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 14936 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 15188 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 14936 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 15192 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 17752 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 18008 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 18556 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 21188 KB Time limit exceeded (wall clock)
13 Execution timed out 16 ms 23532 KB Time limit exceeded (wall clock)
14 Execution timed out 24 ms 25712 KB Time limit exceeded (wall clock)
15 Execution timed out 29 ms 30568 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 47 ms 38528 KB Time limit exceeded (wall clock)
2 Execution timed out 45 ms 40084 KB Time limit exceeded (wall clock)
3 Execution timed out 45 ms 46496 KB Time limit exceeded (wall clock)
4 Execution timed out 23 ms 25944 KB Time limit exceeded (wall clock)
5 Execution timed out 20 ms 29644 KB Time limit exceeded (wall clock)
6 Execution timed out 33 ms 31308 KB Time limit exceeded (wall clock)
7 Execution timed out 46 ms 37880 KB Time limit exceeded (wall clock)
8 Execution timed out 72 ms 51256 KB Time limit exceeded (wall clock)
9 Execution timed out 106 ms 66584 KB Time limit exceeded (wall clock)
10 Execution timed out 115 ms 75988 KB Time limit exceeded (wall clock)
11 Execution timed out 127 ms 80436 KB Time limit exceeded (wall clock)
12 Execution timed out 150 ms 75432 KB Time limit exceeded (wall clock)
13 Execution timed out 119 ms 76404 KB Time limit exceeded (wall clock)
14 Execution timed out 136 ms 80420 KB Time limit exceeded (wall clock)
15 Execution timed out 198 ms 84316 KB Time limit exceeded (wall clock)
16 Execution timed out 169 ms 91588 KB Time limit exceeded (wall clock)
17 Execution timed out 131 ms 90172 KB Time limit exceeded (wall clock)