oj.uz

Submission #935236

# Submission time Handle Problem Language Result Execution time Memory
935236 2024-02-28T23:58:20 Z OAleksa Regions (IOI09_regions) C++14
13 / 100
 8000 ms 73088 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 2e5 + 69;
const int K = 17;
const int B = 450;
int n, q, r, a[N], cnt[N], st[4 * N];
int timer, tin[N], tout[N], up[N][K];
map<pair<int, int>, int> was;
vector<int> g[N], clr[N];
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 = 2;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 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 15004 KB Output is correct
4 Correct 5 ms 15268 KB Output is correct
5 Correct 12 ms 16056 KB Output is correct
6 Correct 40 ms 15880 KB Output is correct
7 Correct 38 ms 15904 KB Output is correct
8 Correct 81 ms 16196 KB Output is correct
9 Correct 1993 ms 16624 KB Output is correct
10 Correct 426 ms 18924 KB Output is correct
11 Correct 3019 ms 19512 KB Output is correct
12 Execution timed out 8034 ms 20052 KB Time limit exceeded
13 Correct 676 ms 22052 KB Output is correct
14 Correct 7461 ms 22216 KB Output is correct
15 Execution timed out 8058 ms 26976 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8095 ms 33608 KB Time limit exceeded
2 Execution timed out 8007 ms 32840 KB Time limit exceeded
3 Execution timed out 8026 ms 39504 KB Time limit exceeded
4 Execution timed out 8063 ms 22284 KB Time limit exceeded
5 Execution timed out 8096 ms 23704 KB Time limit exceeded
6 Incorrect 7334 ms 30232 KB Output isn't correct
7 Execution timed out 8013 ms 32288 KB Time limit exceeded
8 Execution timed out 8051 ms 41728 KB Time limit exceeded
9 Execution timed out 8082 ms 46528 KB Time limit exceeded
10 Execution timed out 8005 ms 63400 KB Time limit exceeded
11 Execution timed out 8077 ms 53224 KB Time limit exceeded
12 Execution timed out 8099 ms 55388 KB Time limit exceeded
13 Execution timed out 8032 ms 57052 KB Time limit exceeded
14 Execution timed out 8006 ms 57100 KB Time limit exceeded
15 Execution timed out 8069 ms 62288 KB Time limit exceeded
16 Execution timed out 8085 ms 73088 KB Time limit exceeded
17 Execution timed out 8007 ms 71232 KB Time limit exceeded