oj.uz

답안 #935679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935679 2024-02-29T11:13:17 Z OAleksa Regions (IOI09_regions) C++14
3 / 100
 196 ms 75272 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], lc[R * K], rc[R * K];
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

# 결과 실행 시간 메모리 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 15244 KB Output isn't correct
4 Incorrect 4 ms 15252 KB Output isn't correct
5 Incorrect 6 ms 15540 KB Output isn't correct
6 Correct 12 ms 15600 KB Output is correct
7 Incorrect 16 ms 15448 KB Output isn't correct
8 Incorrect 21 ms 16040 KB Output isn't correct
9 Correct 32 ms 16964 KB Output is correct
10 Incorrect 52 ms 16812 KB Output isn't correct
11 Incorrect 91 ms 18300 KB Output isn't correct
12 Incorrect 93 ms 18736 KB Output isn't correct
13 Incorrect 135 ms 21328 KB Output isn't correct
14 Runtime error 31 ms 40528 KB Execution killed with signal 11
15 Correct 196 ms 24224 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 44388 KB Execution killed with signal 11
2 Runtime error 53 ms 48632 KB Execution killed with signal 11
3 Runtime error 55 ms 56456 KB Execution killed with signal 11
4 Runtime error 33 ms 40948 KB Execution killed with signal 11
5 Runtime error 38 ms 43616 KB Execution killed with signal 11
6 Runtime error 47 ms 42656 KB Execution killed with signal 11
7 Runtime error 47 ms 48372 KB Execution killed with signal 11
8 Runtime error 49 ms 47440 KB Execution killed with signal 11
9 Runtime error 65 ms 59848 KB Execution killed with signal 11
10 Runtime error 80 ms 63568 KB Execution killed with signal 11
11 Runtime error 81 ms 54872 KB Execution killed with signal 11
12 Runtime error 83 ms 52772 KB Execution killed with signal 11
13 Runtime error 78 ms 57796 KB Execution killed with signal 11
14 Runtime error 80 ms 53960 KB Execution killed with signal 11
15 Runtime error 99 ms 75272 KB Execution killed with signal 11
16 Runtime error 86 ms 58992 KB Execution killed with signal 11
17 Runtime error 96 ms 62224 KB Execution killed with signal 11