oj.uz

Submission #935240

# Submission time Handle Problem Language Result Execution time Memory
935240 2024-02-29T00:28:18 Z OAleksa Regions (IOI09_regions) C++14
13 / 100
 8000 ms 49332 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], st[K * N], lc[K * N], rc[K * N], root[N];
int timer, tin[N], tout[N], up[N][K];
map<pair<int, int>, int> was;
vector<int> g[N], clr[R];
void modify(int v, int tl, int tr, int pos, int x) {
	if (tl == tr)
		st[v] += x;
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid)
			modify(v * 2, tl, mid, pos, x);
		else
			modify(v * 2 + 1, mid + 1, tr, pos, x);
		st[v] = st[v * 2] + st[v * 2 + 1];
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return get(v * 2, tl, mid, l, r) + get(v * 2 + 1, mid + 1, tr, l, r);
	}
}
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;
	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) {
				pair<int, int> f = {tin[x], tout[x]};
				pair<int, int> s = {tin[y], tout[y]};
				return f < s;	
			});
  	}
  	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) {
  			//pokreni dfs iz svakog
  			for (auto i : clr[r1]) {
  				function<void(int, int)> dfs = [&](int v, int p) {
  					ans += (a[v] == r2);
  					for (auto u : g[v]) {
  						if (u == p)
  							continue;
  						dfs(u, v);
  					}
  				};
  				dfs(i, up[i][0]);
  			}
  		}
  		else {
  			//offline kveriz
  			//[l, r] 
  			vector<pair<int, int>> kv;
  			for (auto i : clr[r2]) 
  				kv.push_back({tin[i], tout[i]});
  			sort(kv.begin(), kv.end());
  			int ptr = 0, m = clr[r1].size();
  			for (auto i : kv) {
  				int l, r;
  				tie(l, r) = i;
  				while (ptr < m && tin[clr[r1][ptr]] < l) {
  					modify(1, 1, n, tout[clr[r1][ptr]], 1);
  					ptr++;
  				}
  				ans += get(1, 1, n, r, n);
  			}
  		}
  		//nsqrtnlogn
  		cout << ans << endl;
  		if (!was.count({r1, r2}))
  			was[{r1, r2}] = ans;
  	}
  }
  return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10900 KB Output is correct
4 Correct 4 ms 11160 KB Output is correct
5 Correct 10 ms 11376 KB Output is correct
6 Correct 35 ms 11548 KB Output is correct
7 Correct 33 ms 11804 KB Output is correct
8 Correct 74 ms 11872 KB Output is correct
9 Correct 1902 ms 12892 KB Output is correct
10 Correct 414 ms 12676 KB Output is correct
11 Correct 3102 ms 12972 KB Output is correct
12 Execution timed out 8069 ms 15152 KB Time limit exceeded
13 Correct 734 ms 15668 KB Output is correct
14 Correct 7117 ms 16252 KB Output is correct
15 Execution timed out 8036 ms 18088 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8077 ms 22832 KB Time limit exceeded
2 Execution timed out 8092 ms 24264 KB Time limit exceeded
3 Execution timed out 8090 ms 27644 KB Time limit exceeded
4 Execution timed out 8029 ms 15500 KB Time limit exceeded
5 Execution timed out 8058 ms 17392 KB Time limit exceeded
6 Incorrect 7588 ms 23324 KB Output isn't correct
7 Execution timed out 8021 ms 21456 KB Time limit exceeded
8 Execution timed out 8100 ms 29528 KB Time limit exceeded
9 Execution timed out 8100 ms 29692 KB Time limit exceeded
10 Execution timed out 8009 ms 43356 KB Time limit exceeded
11 Execution timed out 8058 ms 31324 KB Time limit exceeded
12 Execution timed out 8098 ms 34636 KB Time limit exceeded
13 Execution timed out 8087 ms 35376 KB Time limit exceeded
14 Execution timed out 8087 ms 35608 KB Time limit exceeded
15 Execution timed out 8085 ms 40052 KB Time limit exceeded
16 Execution timed out 8023 ms 49332 KB Time limit exceeded
17 Execution timed out 8006 ms 47412 KB Time limit exceeded