oj.uz

Submission #935655

# Submission time Handle Problem Language Result Execution time Memory
935655 2024-02-29T10:31:35 Z OAleksa Regions (IOI09_regions) C++14
25 / 100
 8000 ms 131072 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;
const int M = N * K;
int n, q, r, a[N], cnt[R];
int timer, tin[N], tout[N], up[N][K];
int st1[M], lc1[M], rc1[M];
int root1[N], node1;
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)
		st1[v] = st1[v1] + 1;
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid) {
			lc1[v] = ++node1;
			rc1[v] = rc1[v1];
			modify(lc1[v], lc1[v1], tl, mid, pos);
		}
		else {
			rc1[v] = ++node1;
			lc1[v] = lc1[v1];
			modify(rc1[v], rc1[v1], mid + 1, tr, pos);
		}
		st1[v] = st1[lc1[v]] + st1[rc1[v]];
	}
}

int get(int v, int v1, int tl, int tr, int pos) {
	if (tl == tr)
		return st1[v1] - st1[v];
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid)
			return get(lc1[v], lc1[v1], tl, mid, pos);
		else
			return get(rc1[v], rc1[v1], 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;
	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 <= n;i++) {
  		root1[i] = ++node1;
  		modify(root1[i], root1[i - 1], 1, n, a[b[i - 1]]);
  	}
  	for (int i = 1;i <= r;i++) 
			sort(clr[i].begin(), clr[i].end());
  	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) {
  			for (auto i : clr[r1]) 
  				ans += get(root1[tin[i] - 1], root1[tout[i]], 1, n, r2);
  		}
  		else {
  			ans = 0;
  		}
  		//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 2 ms 14936 KB Output is correct
3 Correct 4 ms 15012 KB Output is correct
4 Correct 5 ms 15272 KB Output is correct
5 Correct 6 ms 15312 KB Output is correct
6 Correct 14 ms 15880 KB Output is correct
7 Correct 17 ms 15460 KB Output is correct
8 Correct 25 ms 15512 KB Output is correct
9 Correct 30 ms 18864 KB Output is correct
10 Correct 62 ms 20968 KB Output is correct
11 Correct 112 ms 22032 KB Output is correct
12 Correct 124 ms 21372 KB Output is correct
13 Correct 163 ms 25636 KB Output is correct
14 Correct 264 ms 26604 KB Output is correct
15 Correct 442 ms 33600 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2387 ms 43628 KB Output isn't correct
2 Incorrect 2130 ms 42312 KB Output isn't correct
3 Incorrect 4019 ms 53080 KB Output isn't correct
4 Correct 293 ms 27448 KB Output is correct
5 Correct 359 ms 31624 KB Output is correct
6 Incorrect 500 ms 37848 KB Output isn't correct
7 Incorrect 668 ms 41628 KB Output isn't correct
8 Incorrect 1356 ms 56608 KB Output isn't correct
9 Execution timed out 8063 ms 75024 KB Time limit exceeded
10 Execution timed out 8020 ms 83632 KB Time limit exceeded
11 Execution timed out 8015 ms 76776 KB Time limit exceeded
12 Incorrect 4789 ms 75884 KB Output isn't correct
13 Incorrect 7724 ms 79188 KB Output isn't correct
14 Runtime error 2342 ms 131072 KB Execution killed with signal 9
15 Runtime error 4132 ms 131072 KB Execution killed with signal 9
16 Execution timed out 8012 ms 86332 KB Time limit exceeded
17 Runtime error 2376 ms 131072 KB Execution killed with signal 9