oj.uz

Submission #943569

# Submission time Handle Problem Language Result Execution time Memory
943569 2024-03-11T15:27:59 Z NK_ Traffickers (RMI18_traffickers) C++17
0 / 100
 83 ms 120144 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;

		int len = dep[a] + dep[b] - 2 * dep[l];

		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(end(path), begin(dpath), end(dpath));

		assert(len == sz(path));
		assert(sz(path) <= 25);

		// 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);
	}

	exit(0);

	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 << " => ";
				// cout << 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 51 ms 105556 KB Execution killed with signal 6
2 Runtime error 49 ms 106072 KB Execution killed with signal 6
3 Runtime error 47 ms 105808 KB Execution killed with signal 6

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 109720 KB Execution killed with signal 6
2 Runtime error 58 ms 108884 KB Execution killed with signal 6
3 Runtime error 53 ms 110416 KB Execution killed with signal 6
4 Runtime error 59 ms 110164 KB Execution killed with signal 6
5 Runtime error 52 ms 109400 KB Execution killed with signal 6
6 Runtime error 60 ms 109648 KB Execution killed with signal 6
7 Runtime error 52 ms 109652 KB Execution killed with signal 6
8 Runtime error 68 ms 109960 KB Execution killed with signal 6
9 Runtime error 56 ms 110416 KB Execution killed with signal 6

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 117584 KB Execution killed with signal 6
2 Runtime error 68 ms 119636 KB Execution killed with signal 6
3 Runtime error 83 ms 118356 KB Execution killed with signal 6
4 Runtime error 64 ms 116308 KB Execution killed with signal 6
5 Runtime error 79 ms 115796 KB Execution killed with signal 6
6 Runtime error 67 ms 119640 KB Execution killed with signal 6
7 Runtime error 82 ms 120144 KB Execution killed with signal 6
8 Runtime error 67 ms 118864 KB Execution killed with signal 6