oj.uz

Submission #935684

# Submission time Handle Problem Language Result Execution time Memory
935684 2024-02-29T11:30:22 Z OAleksa Regions (IOI09_regions) C++14
60 / 100
 8000 ms 107132 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]);
  			}
  		}
  		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 3 ms 14936 KB Output is correct
3 Correct 3 ms 15000 KB Output is correct
4 Correct 4 ms 15008 KB Output is correct
5 Correct 7 ms 15068 KB Output is correct
6 Correct 12 ms 15676 KB Output is correct
7 Correct 16 ms 15940 KB Output is correct
8 Correct 21 ms 16000 KB Output is correct
9 Correct 33 ms 18872 KB Output is correct
10 Correct 53 ms 19184 KB Output is correct
11 Correct 89 ms 20128 KB Output is correct
12 Correct 107 ms 23060 KB Output is correct
13 Correct 171 ms 23804 KB Output is correct
14 Correct 352 ms 25640 KB Output is correct
15 Correct 518 ms 32452 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3190 ms 42732 KB Output is correct
2 Correct 4070 ms 42768 KB Output is correct
3 Correct 5061 ms 53288 KB Output is correct
4 Correct 192 ms 27088 KB Output is correct
5 Correct 253 ms 32144 KB Output is correct
6 Correct 474 ms 34908 KB Output is correct
7 Correct 612 ms 40136 KB Output is correct
8 Correct 1820 ms 55416 KB Output is correct
9 Correct 2520 ms 75648 KB Output is correct
10 Execution timed out 8093 ms 85520 KB Time limit exceeded
11 Execution timed out 8061 ms 91228 KB Time limit exceeded
12 Execution timed out 8058 ms 81308 KB Time limit exceeded
13 Execution timed out 8045 ms 83132 KB Time limit exceeded
14 Execution timed out 8010 ms 85272 KB Time limit exceeded
15 Execution timed out 8066 ms 95692 KB Time limit exceeded
16 Execution timed out 8006 ms 96632 KB Time limit exceeded
17 Execution timed out 8058 ms 107132 KB Time limit exceeded