oj.uz

Submission #491334

# Submission time Handle Problem Language Result Execution time Memory
491334 2021-12-01T14:54:47 Z valerikk Traffickers (RMI18_traffickers) C++17
100 / 100
 1374 ms 87068 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e4 + 5;
const int Q = 1e5 + 7;
const int L = 16;
const int M = 20;

struct {
	int f[N];

	void add(int i, int delta) {
		for (++i; i < N; i += i & -i) {
			f[i] += delta;
		}
	}

	void add(int l, int r, int delta) {
		add(l, delta);
		add(r, -delta);
	}

	int get(int i) {
		int res = 0;
		for (++i; i > 0; i -= i & -i) {
			res += f[i];
		}
		return res;
	}
} f[M + 1][M];

int n;
vector<int> g[N];
int par[N];
int tin[N], tout[N], first[N], tt;
vector<int> ord;

void dfs(int v, int p = -1) {
	par[v] = p;
	tin[v] = tt++;
	first[v] = ord.size();
	ord.push_back(v);
	for (int u : g[v]) {
		if (u != p) {
			dfs(u, v);
			ord.push_back(v);
		}
	}	
	tout[v] = tt;
}

pair<int, int> st[L + 1][2 * N];

int lca(int u, int v) {
	int l = first[u], r = first[v];
	if (l > r) {
		swap(l, r);
	}
	++r;
	int lg = 31 - __builtin_clz(r - l);
	return min(st[lg][l], st[lg][r - (1 << lg)]).second;
}

vector<int> find_path(int u, int v) {
	int w = lca(u, v);
	vector<int> path_u, path_v;
	while (u != w) {
		path_u.push_back(u);
		u = par[u];
	}
	while (v != w) {
		path_v.push_back(v);
		v = par[v];
	}
	vector<int> path;
	path.insert(path.begin(), path_u.begin(), path_u.end());
	path.push_back(w);
	reverse(path_v.begin(), path_v.end());
	path.insert(path.end(), path_v.begin(), path_v.end());
	return path;
}

int kek[N][M + 1][M];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);

	for (int i = 0; i < 2 * n - 1; ++i) {
		st[0][i] = {tin[ord[i]], ord[i]};
	}
	for (int p = 1; p < L; ++p) {
		for (int i = 0; i + (1 << p) <= 2 * n - 1; ++i) {
			st[p][i] = min(st[p - 1][i], st[p - 1][i + (1 << (p - 1))]);
		}
	}

	int k;
	cin >> k;
	while (k--) {
		int u, v;
		cin >> u >> v;
		
		auto path = find_path(u, v);
		int len = path.size();
		for (int i = 0; i < len; ++i) {
			f[len][i].add(tin[path[i]], tout[path[i]], 1);
			++kek[path[i]][len][i];
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int type, u, v;
		cin >> type >> u >> v;
		
		if (type == 1 || type == 2) {
			auto path = find_path(u, v);
			int len = path.size();
			for (int i = 0; i < len; ++i) {
				f[len][i].add(tin[path[i]], tout[path[i]], 3 - 2 * type);
				kek[path[i]][len][i] += 3 - 2 * type;
			}
		} else {
			int t1, t2;
			cin >> t1 >> t2;
			
			int w = lca(u, v);
			
			long long ans = 0;

			for (int len = 1; len <= M; ++len) {
				for (int i = 0; i < len; ++i) {
					int cnt1 = f[len][i].get(tin[u]) + f[len][i].get(tin[v]) - 2 * f[len][i].get(tin[w]) + kek[w][len][i];
					//if (cnt1 != 0) {
					//	cout << len << " " << i << " " << cnt1 << endl;
					//}
					int cnt2 = t2 / len + (t2 % len >= i);
					if (t1 > 0) {
						cnt2 -= (t1 - 1) / len + ((t1 - 1) % len >= i);
					}
					ans += 1ll * cnt1 * cnt2;
				}
			}

			cout << ans << "\n";
			//return 0;
		}
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 7 ms 8140 KB Output is correct
3 Correct 10 ms 8012 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 31268 KB Output is correct
2 Correct 89 ms 29332 KB Output is correct
3 Correct 98 ms 30760 KB Output is correct
4 Correct 114 ms 31368 KB Output is correct
5 Correct 86 ms 31044 KB Output is correct
6 Correct 85 ms 31172 KB Output is correct
7 Correct 82 ms 30860 KB Output is correct
8 Correct 130 ms 31568 KB Output is correct
9 Correct 83 ms 31812 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1141 ms 86280 KB Output is correct
2 Correct 1374 ms 86964 KB Output is correct
3 Correct 1337 ms 86528 KB Output is correct
4 Correct 1184 ms 85844 KB Output is correct
5 Correct 1259 ms 85432 KB Output is correct
6 Correct 1129 ms 86856 KB Output is correct
7 Correct 971 ms 87068 KB Output is correct
8 Correct 1029 ms 86624 KB Output is correct