oj.uz

Submission #943552

# Submission time Handle Problem Language Result Execution time Memory
943552 2024-03-11T15:12:11 Z NK_ Traffickers (RMI18_traffickers) C++17
0 / 100
 75 ms 120148 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;

const int nax = 3e4+5;
const int T = 21;
const int LG = 16;
int A[T][T][nax];


void upd(int i, int j, int p, int x) { for(++p; p <= nax; p += p & -p) A[i][j][p - 1] += x; }
int qry(int i, int j, int r) { int s = 0; for(; r; r -= r & -r) s += A[i][j][r - 1]; return s; }
int qry(int i, int j, int l, int r) { return qry(i, j, r + 1) - qry(i, j, l); }


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	memset(A, 0, sizeof A);

	int N; cin >> N;

	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	vi st(N), en(N), dep(N); V<vi> up(N, vi(LG)); int tim = 0;
	function<void(int, int)> gen = [&](int u, int p) {
		// cout << u << " <-> " << p << endl;
		st[u] = tim++; dep[u] = (u == p ? 0 : dep[p] + 1); 
		up[u][0] = p; for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1]; 

		for(auto& v : adj[u]) if (v != p) {
			// cout << v << " " << u << endl;
			gen(v, u);
		}

		en[u] = tim - 1;
	};

	gen(0, 0);

	auto lca = [&](int a, int b) {
		if (dep[a] > dep[b]) swap(a, b);
		for(int i = LG - 1; i >= 0; i--) {
			if (!(st[up[a][i]] <= st[b] && en[b] <= en[up[a][i]])) a = up[a][i];
		}
		return up[a][0];
	};	

	auto traf = [&](int a, int b, int d = +1) {
		// cout << a << " " << b << " =====> ";
		int l = lca(a, b);
		// cout << l << endl;

		vi path;
		while(a != l) {
			path.pb(a);
			a = up[a][0];
		}
		
		path.pb(l);

		vi dpath;
		while(b != l) {
			dpath.pb(b);
			b = up[b][0];
		}
		reverse(begin(dpath), end(dpath));

		path.insert(prev(end(path)), begin(dpath), end(dpath));

		for(int r = 0; r < sz(path); r++) {
			upd(r, sz(path), st[path[r]], d);
			upd(r, sz(path), en[path[r]] + 1, -d);
		}

		// for(auto& x : path) cout << x << " ";
		// cout << endl;
	};

	int K; cin >> K;
	for(int i = 0; i < K; i++) {
		int a, b; cin >> a >> b; --a, --b;
		traf(a, b);
	}

	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int t; cin >> t;
		if (t == 1) {
			int a, b; cin >> a >> b; --a, --b;
			traf(a, b);
		} else if (t == 2) {
			int a, b; cin >> a >> b; --a, --b;
			traf(a, b, -1);
		} else if (t == 3) {
			int a, b; ll l, r; cin >> a >> b >> l >> r; --a, --b;
			int p = lca(a, b);

			ll ans = 0;
			for(int len = 1; len <= 20; len++) {
				for(int rem = 0; rem < len; rem++) {
					ll L = (l - rem + len - 1) / len, R = (r - rem) / len;
					ll trafs = qry(rem, len, st[p], st[a]) + qry(rem, len, st[p], st[b]) - qry(rem, len, st[p], st[p]);
					ll times = R - L + 1;
					ans += times * 1LL * trafs;
					// cout << rem << " " << len << endl;
					// cout << a << " " << b << " | " << l << " " << r << " => " << trafs << " || " << L << " " << R << " => " << times << endl;
				}
			}

			cout << ans << nl;
		}
	}


	exit(0-0);
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 105536 KB Execution killed with signal 11
2 Runtime error 49 ms 105956 KB Execution killed with signal 11
3 Runtime error 47 ms 105808 KB Execution killed with signal 11

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 109936 KB Execution killed with signal 11
2 Runtime error 53 ms 108816 KB Execution killed with signal 11
3 Runtime error 54 ms 110236 KB Execution killed with signal 11
4 Runtime error 53 ms 109908 KB Execution killed with signal 11
5 Runtime error 53 ms 109396 KB Execution killed with signal 11
6 Runtime error 59 ms 109684 KB Execution killed with signal 11
7 Runtime error 57 ms 109648 KB Execution killed with signal 11
8 Runtime error 56 ms 109908 KB Execution killed with signal 11
9 Runtime error 57 ms 110268 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 117588 KB Execution killed with signal 11
2 Runtime error 69 ms 119732 KB Execution killed with signal 11
3 Runtime error 75 ms 118352 KB Execution killed with signal 11
4 Runtime error 65 ms 116408 KB Execution killed with signal 11
5 Runtime error 67 ms 115980 KB Execution killed with signal 11
6 Runtime error 66 ms 119696 KB Execution killed with signal 11
7 Runtime error 66 ms 120148 KB Execution killed with signal 11
8 Runtime error 69 ms 118892 KB Execution killed with signal 11