oj.uz

Submission #935673

# Submission time Handle Problem Language Result Execution time Memory
935673 2024-02-29T11:08:54 Z OAleksa Regions (IOI09_regions) C++14
3 / 100
 210 ms 69380 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 * 15], lc[R * 15], rc[R * 15];
int root[N], node;
map<pair<int, int>, int> was;
vector<int> g[N], clr[R];
vector<int> b;
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;
	b.push_back(v);
	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 2 ms 12888 KB Output isn't correct
2 Incorrect 3 ms 12888 KB Output isn't correct
3 Incorrect 3 ms 12960 KB Output isn't correct
4 Incorrect 5 ms 13480 KB Output isn't correct
5 Incorrect 6 ms 13288 KB Output isn't correct
6 Correct 12 ms 13644 KB Output is correct
7 Incorrect 17 ms 13892 KB Output isn't correct
8 Incorrect 19 ms 14268 KB Output isn't correct
9 Correct 34 ms 14456 KB Output is correct
10 Incorrect 60 ms 15204 KB Output isn't correct
11 Incorrect 85 ms 16064 KB Output isn't correct
12 Incorrect 100 ms 17180 KB Output isn't correct
13 Incorrect 117 ms 18120 KB Output isn't correct
14 Runtime error 27 ms 32996 KB Execution killed with signal 11
15 Correct 210 ms 23320 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 36940 KB Execution killed with signal 11
2 Runtime error 42 ms 45768 KB Execution killed with signal 11
3 Runtime error 52 ms 49796 KB Execution killed with signal 11
4 Runtime error 29 ms 33300 KB Execution killed with signal 11
5 Runtime error 33 ms 40264 KB Execution killed with signal 11
6 Runtime error 35 ms 39480 KB Execution killed with signal 11
7 Runtime error 46 ms 45452 KB Execution killed with signal 11
8 Runtime error 55 ms 44928 KB Execution killed with signal 11
9 Runtime error 64 ms 53204 KB Execution killed with signal 11
10 Runtime error 97 ms 61968 KB Execution killed with signal 11
11 Runtime error 82 ms 53028 KB Execution killed with signal 11
12 Runtime error 76 ms 50760 KB Execution killed with signal 11
13 Runtime error 77 ms 55728 KB Execution killed with signal 11
14 Runtime error 85 ms 52044 KB Execution killed with signal 11
15 Runtime error 97 ms 69380 KB Execution killed with signal 11
16 Runtime error 92 ms 61704 KB Execution killed with signal 11
17 Runtime error 82 ms 53232 KB Execution killed with signal 11