oj.uz

Submission #491333

# Submission time Handle Problem Language Result Execution time Memory
491333 2021-12-01T14:53:23 Z valerikk Traffickers (RMI18_traffickers) C++17
15 / 100
 3500 ms 86648 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;
					//}
					for (int t = t1; t <= t2; ++t) {
						if (t % len == i) {
							ans += cnt1;
						}
					}
					/*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 5904 KB Output is correct
2 Correct 8 ms 8140 KB Output is correct
3 Correct 7 ms 8092 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3557 ms 31304 KB Time limit exceeded
2 Execution timed out 3544 ms 29224 KB Time limit exceeded
3 Execution timed out 3578 ms 30924 KB Time limit exceeded
4 Execution timed out 3574 ms 31360 KB Time limit exceeded
5 Execution timed out 3553 ms 31052 KB Time limit exceeded
6 Execution timed out 3546 ms 31308 KB Time limit exceeded
7 Execution timed out 3571 ms 31044 KB Time limit exceeded
8 Execution timed out 3576 ms 31768 KB Time limit exceeded
9 Execution timed out 3576 ms 31948 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3560 ms 85572 KB Time limit exceeded
2 Execution timed out 3581 ms 86340 KB Time limit exceeded
3 Execution timed out 3586 ms 85940 KB Time limit exceeded
4 Execution timed out 3587 ms 85120 KB Time limit exceeded
5 Execution timed out 3568 ms 84568 KB Time limit exceeded
6 Execution timed out 3583 ms 86224 KB Time limit exceeded
7 Execution timed out 3566 ms 86648 KB Time limit exceeded
8 Execution timed out 3566 ms 86088 KB Time limit exceeded