Submission #828471

#	Time	Username	Problem	Language	Result	Execution time	Memory
828471		khshg	Two Currencies (JOI23_currencies)	C++14	100 / 100	829 ms	31200 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int N, M, Q;
vector<vector<int>> adj;
vector<int> par, sz, anc, flat, pos;
vector<pair<int, int>> e, ch;
vector<int> S, T, X;
vector<long long> Y;

void dfs_sz(int s) {
	sz[s] = 1;
	if(adj[s][0] == par[s] && (int)adj[s].size() >= 2) swap(adj[s][0], adj[s][1]);
	for(auto& u : adj[s]) {
		if(u == par[s]) continue;
		par[u] = s;
		dfs_sz(u);
		sz[s] += sz[u];
		if(sz[adj[s][0]] < sz[u]) swap(adj[s][0], u);
	}
}

void build_hld(int s, int r) {
	pos[s] = (int)flat.size();
	flat.pb(s);
	anc[s] = r;
	for(auto& u : adj[s]) {
		if(u == par[s]) continue;
		build_hld(u, (u == adj[s][0] ? r : u));
	}
}

int LCA(int a, int b) {
	if(pos[a] > pos[b]) swap(a, b);
	if(anc[a] == anc[b]) return a;
	return LCA(a, par[anc[b]]);
}

vector<long long> bit;
void update(int ind, long long val) {
	++ind;
	while(ind <= N) {
		bit[ind] += val;
		ind += ind & -ind;
	}
}
long long pref_sum(int ind) {
	++ind;
	long long sum = 0;
	while(ind > 0) {
		sum += bit[ind];
		ind -= ind & -ind;
	}
	return sum;
}
long long Query(int l, int r) {
	return pref_sum(r) - pref_sum(l - 1);
}

long long hld_path(int u, int v) {
	if(anc[u] == anc[v]) return Query(pos[v], pos[u]);
	return Query(pos[anc[u]], pos[u]) + hld_path(par[anc[u]], v);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> M >> Q;
	adj.resize(N);
	e.resize(N - 1);
	for(int i = 0; i + 1 < N; ++i) {
		int u, v; cin >> u >> v; --u; --v;
		e[i] = {u, v};
		adj[u].pb(v);
		adj[v].pb(u);
	}
	{ // hld
		par.resize(N);
		sz.resize(N);
		par[0] = -1;
		dfs_sz(0);
		anc.resize(N);
		pos.resize(N);
		build_hld(0, -1);
	}
	for(int i = 0; i + 1 < N; ++i) {
		if(par[e[i].second] == e[i].first) swap(e[i].first, e[i].second);
	}
	for(int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y;
		ch.pb({y, e[x - 1].first});
	}
	sort(begin(ch), end(ch));
	S.resize(Q);
	T.resize(Q);
	X.resize(Q);
	Y.resize(Q);
	for(int i = 0; i < Q; ++i) {
		cin >> S[i] >> T[i] >> X[i] >> Y[i];
		--S[i]; --T[i];
	}
	vector<int> TL(Q, 0), TR(Q, M);
	while(true) {
		bool any = false;
		vector<vector<int>> Pos(M + 1);
		for(int i = 0; i < Q; ++i) {
			if(TL[i] == TR[i]) continue;
			any = true;
			int TM = (TL[i] + TR[i] + 1) / 2;
			Pos[TM].pb(i);
		}
		if(!any) break;
		bit = vector<long long>(N + 1, 0LL);
		for(int i = 0; i < M; ++i) {
			update(pos[ch[i].second], ch[i].first);
			for(auto& u : Pos[i + 1]) {
				int L = LCA(S[u], T[u]);
				long long sum = hld_path(S[u], L) + hld_path(T[u], L) - 2 * hld_path(L, L);
				if(sum <= Y[u]) {
					TL[u] = i + 1;
				} else {
					TR[u] = i;
				}
			}
		}
	}
	vector<int> ans(Q);
	bit = vector<long long>(N + 1, 0LL);
	vector<vector<int>> Pos(M + 1);
	for(int i = 0; i < Q; ++i) {
		Pos[TL[i]].pb(i);
	}
	for(int i = M; i >= 0; --i) {
		if(i < M) update(pos[ch[i].second], 1);
		for(int& u : Pos[i]) {
			if(i == M) {
				ans[u] = X[u];
				continue;
			}
			int L = LCA(S[u], T[u]);
			long long sum = hld_path(S[u], L) + hld_path(T[u], L) - 2 * hld_path(L, L);
			ans[u] = max(-1LL, X[u] - sum);
		}
	}
	for(auto& u : ans) {
		cout << u << '\n';
	}
	return 0;
}

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