Submission #1235580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235580		JooDdae	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	5956 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

struct Node {
	ll s;
	int c, l, r;
} t[5005005];
int r[100100], cnt;

int n, m, k, x[100100], y[100100], a[100100], c[100100], lev[100100], sp[100100][20];
vector<int> v[100100], in[100100];
vector<array<int, 2>> C;

int update(int u, int id, int l = 0, int r = m-1) {
	if(id < l || r < id) return u;

	int x = ++cnt;
	t[x] = t[u], t[x].s += C[id][0], t[x].c++;
	if(l == r) return x;

	t[x].l = update(t[x].l, id, l, mid);
	t[x].r = update(t[x].r, id, mid+1, r);
	return x;
}

int find(int a, int b, int c, int d, ll s, int l = 0, int r = m-1) {
	if(t[c].c+t[d].c-t[a].c-t[b].c <= 1) return s < t[c].s+t[d].s-t[a].s-t[b].s;
	
	ll ls = t[t[c].l].s+t[t[d].l].s-t[t[a].l].s-t[t[b].l].s;
	if(ls > s) return find(t[a].l, t[b].l, t[c].l, t[d].l, s, l, mid) + t[t[c].r].c+t[t[d].r].c-t[t[a].r].c-t[t[b].r].c;
	return find(t[a].r, t[b].r, t[c].r, t[d].r, s-ls, mid+1, r);
}

void dfs(int u, int p) {
	sp[u][0] = p, lev[u] = lev[p]+1;
	for(int i=1;i<20;i++) sp[u][i] = sp[sp[u][i-1]][i-1];
	r[u] = r[p];
	for(auto i : in[u]) if(x[a[i]] == p || y[a[i]] == p) r[u] = update(r[u], c[i]);
	for(auto x : v[u]) if(x != p) dfs(x, u);
}

int lca(int x, int y) {
	if(lev[x] < lev[y]) swap(x, y);
	for(int i=0;i<20;i++) if((1 << i) & (lev[x]-lev[y])) x = sp[x][i];
	if(x == y) return x;
	for(int i=19;i>=0;i--) if(sp[x][i] != sp[y][i]) x = sp[x][i], y = sp[y][i];
	return sp[x][0];
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> k;
	for(int i=1;i<n;i++) {
		cin >> x[i] >> y[i];
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	for(int i=1;i<=m;i++) {
		cin >> a[i] >> c[i];
		C.push_back({c[i], i});
		in[x[a[i]]].push_back(i);
		in[y[a[i]]].push_back(i);
	}
	sort(C.begin(), C.end());
	for(int i=0;i<m;i++) c[C[i][1]] = i;
	dfs(1, 0);

	while(k--) {
		ll s, e, G, S; cin >> s >> e >> G >> S;
		int L = lca(s, e);
		find(r[sp[L][0]], r[L], r[s], r[e], S);
		cout << max(G-find(r[sp[L][0]], r[L], r[s], r[e], S), -1ll) << "\n";
	}
}

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