Submission #491334

#	Time	Username	Problem	Language	Result	Execution time	Memory
491334		valerikk	Traffickers (RMI18_traffickers)	C++17	100 / 100	1374 ms	87068 KiB

traffickers

#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 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40