Submission #792697

#	Time	Username	Problem	Language	Result	Execution time	Memory
792697		vjudge1	Two Currencies (JOI23_currencies)	C++17	100 / 100	619 ms	88168 KiB

currencies

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

struct query {
	int s, t, x, y;
	query(int s, int t, int x, int y) : s(s), t(t), x(x), y(y) {}
};

vi pos, G[mxN];
vii edges, points;
vector<query> queries;
pii euler_tour[20][2 * mxN];
int n, m, q, a[mxN], ans[mxN], cp[mxN];
int tin[mxN], tout[mxN], dep[mxN], ap[mxN], timer, ecnt;

void dfs(int v, int p) {
	tin[v] = ++timer, dep[v] = dep[p] + 1;
	euler_tour[0][++ecnt] = pair{dep[v], v}, ap[v] = ecnt;

	for(int u : G[v]) {
		if(u == p) continue;
		dfs(u, v);
		euler_tour[0][++ecnt] = pair{dep[v], v};
	}

	tout[v] = timer;
}

void build_sparse() {
	for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i)
		for(int j = 1; j <= ecnt - (p << 1) + 1; ++j)
			euler_tour[i][j] = min(euler_tour[i - 1][j], euler_tour[i - 1][j + p]);
}

int LCA(int u, int v) {
	int l = ap[u], r = ap[v];
	if(l > r) swap(l, r);
	int len = r - l + 1, lg_len = __lg(len);
	return min(euler_tour[lg_len][l], euler_tour[lg_len][r - (1 << lg_len) + 1]).ss;
}

pii fenw[mxN];

void update(int idx, int val1, int val2) {
	for(; idx <= n; idx += (idx & (-idx)))
		fenw[idx].ff += val1, fenw[idx].ss += val2;
}

void update_range(int l, int r, int val1, int val2) {
	update(l, val1, val2);
	update(r + 1, -val1, -val2);
}

pii get(int idx) {
	pii res = pair{0, 0};
	for(; idx; idx -= (idx & (-idx)))
		res.ff += fenw[idx].ff, res.ss += fenw[idx].ss;
	return res;
}

pii add(pii x, pii y) {
	return pair{x.ff + y.ff, x.ss + y.ss};
}

pii sub(pii x, pii y) {
	return pair{x.ff - y.ff, x.ss - y.ss};
}

pii mul(pii x, int val) {
	return pair{x.ff * val, x.ss * val};
}

void pbs(int l, int r, vi &all_query) {
	if(l > r) return;

	vi left, right;
	int mid = (l + r) >> 1;

	for(int i = l; i <= mid; ++i) {
		pii tmp = points[i], edge = edges[tmp.ff];
		if(dep[edge.ff] > dep[edge.ss]) swap(edge.ff, edge.ss);
		update_range(tin[edge.ss], tout[edge.ss], tmp.ss, 1);
	}

	for(auto &idx : all_query) {
		auto [s, t, x, y] = queries[idx];
		int lca = LCA(s, t);
		
		pii res = pair{0, 0};
		res = add(res, get(tin[s]));
		res = add(res, get(tin[t]));
		res = sub(res, mul(get(tin[lca]), 2));

		if(res.ff <= y) {
			ans[idx] = max(ans[idx], x - (cp[s] + cp[t] - 2 * cp[lca] - res.ss));
			right.emplace_back(idx);
		}
		else left.emplace_back(idx);
	}

	if(l == r) {
		pii tmp = points[mid], edge = edges[tmp.ff];
		if(dep[edge.ff] > dep[edge.ss]) swap(edge.ff, edge.ss);
		update_range(tin[edge.ss], tout[edge.ss], -tmp.ss, -1);
		return;
	}
	
	if(!right.empty()) {
		pbs(mid + 1, r, right);
	}

	for(int i = l; i <= mid; ++i) {
		pii tmp = points[i], edge = edges[tmp.ff];
		if(dep[edge.ff] > dep[edge.ss]) swap(edge.ff, edge.ss);
		update_range(tin[edge.ss], tout[edge.ss], -tmp.ss, -1);
	}

	if(!left.empty()) {
		pbs(l, mid - 1, left);
	}
}

void solve() {
	cin >> n >> m >> q;
	for(int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		edges.emplace_back(u, v);
	}
	dfs(1, 0);
	build_sparse();

	for(int i = 1; i <= m; ++i) {
		int p, c; cin >> p >> c;
		points.emplace_back(--p, c);
		pii edge = edges[p];
		if(dep[edge.ff] > dep[edge.ss])
			swap(edge.ff, edge.ss);
		++cp[edge.ss];
	}

	auto dfs_cp = [&](auto self, int v, int p) -> void {
		for(int u : G[v]) {
			if(u == p) continue;
			cp[u] += cp[v];
			self(self, u, v);
		}
	};
	dfs_cp(dfs_cp, 1, 0);

	sort(all(points), [&](pii &x, pii &y) {
		return x.ss < y.ss;
	});

	for(int i = 1; i <= q; ++i) {
		int s, t, x, y;
		cin >> s >> t >> x >> y;
		queries.emplace_back(s, t, x, y);
		int lca = LCA(s, t);
		ans[i - 1] = max(-1ll, x - (cp[s] + cp[t] - 2 * cp[lca]));
	}

	vi idx(q); iota(all(idx), 0);
	pbs(0, m - 1, idx);

	for(int i = 0; i < q; ++i)
		cout << ans[i] << "\n";
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1; //cin >> t;
	while(t--) solve();

#ifdef CDuongg
	auto end = chrono::high_resolution_clock::now();
	cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
	cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32