oj.uz

Submission #935681

# Submission time Handle Problem Language Result Execution time Memory
935681 2024-02-29T11:14:20 Z OAleksa Regions (IOI09_regions) C++14
8 / 100
 8000 ms 113128 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 += R - L + 1;
  			}
  		}
  		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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14936 KB Output isn't correct
2 Incorrect 4 ms 14936 KB Output isn't correct
3 Incorrect 4 ms 15000 KB Output isn't correct
4 Incorrect 4 ms 15272 KB Output isn't correct
5 Incorrect 6 ms 15304 KB Output isn't correct
6 Correct 12 ms 15664 KB Output is correct
7 Incorrect 18 ms 16184 KB Output isn't correct
8 Incorrect 22 ms 15972 KB Output isn't correct
9 Correct 34 ms 18528 KB Output is correct
10 Incorrect 56 ms 19060 KB Output isn't correct
11 Incorrect 79 ms 11888 KB Output isn't correct
12 Incorrect 108 ms 23172 KB Output isn't correct
13 Incorrect 120 ms 23752 KB Output isn't correct
14 Incorrect 163 ms 25392 KB Output isn't correct
15 Correct 211 ms 32020 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1423 ms 42136 KB Output isn't correct
2 Incorrect 1284 ms 43212 KB Output isn't correct
3 Correct 1630 ms 54248 KB Output is correct
4 Incorrect 185 ms 26388 KB Output isn't correct
5 Incorrect 256 ms 32584 KB Output isn't correct
6 Incorrect 472 ms 34744 KB Output isn't correct
7 Incorrect 569 ms 36340 KB Output isn't correct
8 Incorrect 1139 ms 48228 KB Output isn't correct
9 Incorrect 1707 ms 71372 KB Output isn't correct
10 Execution timed out 8083 ms 86120 KB Time limit exceeded
11 Incorrect 3203 ms 93156 KB Output isn't correct
12 Incorrect 1180 ms 81408 KB Output isn't correct
13 Incorrect 1620 ms 84460 KB Output isn't correct
14 Execution timed out 8032 ms 88160 KB Time limit exceeded
15 Incorrect 2874 ms 100736 KB Output isn't correct
16 Incorrect 2731 ms 102344 KB Output isn't correct
17 Incorrect 6933 ms 113128 KB Output isn't correct