Submission #943606

#	Time	Username	Problem	Language	Result	Execution time	Memory
943606		NK_	Traffickers (RMI18_traffickers)	C++17	25 / 100	1347 ms	60224 KiB

traffickers

// 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);
		int d = dep[a] - dep[b];
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) a = up[a][i];

		if (a == b) return a;

		for(int i = LG - 1; i >= 0; i--) {
			if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][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 + 1 == sz(path));
		assert(len + 1 <= 20);

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

	auto inside = [&](int a, int b, int c) {
       if (a > b) return false;
       return a <= c && c <= b;
	};

	auto compute = [&](int rem, int mod, ll L, ll R) {
		ll bl = L / mod, br = R / mod;
		ll ans = 0;

		if (bl == br) {	
			ans += inside(L % mod, R % mod, rem);
		} else {
			ans += br - bl - 1;
			ans += inside(L % mod, mod - 1, rem);
			ans += inside(0, R % mod, rem);
		}

		return ans;
	};


	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++) {
				// cout << r - rem << " " << (r - rem) / len << endl;

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

			cout << ans << nl;
		}
	}


	exit(0-0);
}

• Subtask 1: 10 / 15
• Subtask 2: 5 / 45
• Subtask 3: 10 / 40