Submission #1231543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231543		g4yuhg	Two Currencies (JOI23_currencies)	C++20	100 / 100	1457 ms	46496 KiB

currencies

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100005
using namespace std;

bool ghuy4g;

struct Canh {
	ll u, v;
} canh[N];
struct QR {
	ll s, t, x, y;
} qr[N];

ll n, m, q, in[N + 1], out[N + 1], par[N + 1][LOG + 2], sz[N + 1], f[N + 1];
ll high[N + 1];
ll bit[N + 1], bit1[N + 1];

vector<ll> adj[N + 1];
pii p[N + 1];
ll timer = 0;

void prepare() {
    for (int j = 1; j <= LOG; j ++) {
        for (int i = 1; i <= n; i ++) {
            ll p = par[i][j - 1];
            if (p != 0) par[i][j] = par[p][j - 1];
        }
    }
}
ll lca(ll u, ll v) {
    if (high[u] < high[v]) swap(u, v);
    for (int j = LOG; j >= 0; j --) {
        if (par[u][j] != 0 && high[u] - (1 << j) >= high[v]) {
            u = par[u][j];
        }
    }
    if (u == v) return u;
    for (int j = LOG; j >= 0; j --) {
        if (par[u][j] != 0 && par[v][j] != 0 && par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

void update(ll u, ll v) {
    auto bit_update = [&](ll b[], int idx, ll val) {
        for (; idx <= n; idx += idx & -idx) {
            b[idx] += val;
        }
    };
    bit_update(bit, in[u], v);
    bit_update(bit, out[u] + 1, -v);
    bit_update(bit1, in[u], 1);
    bit_update(bit1, out[u] + 1, -1);
}

ll get(ll u, ll v) {
    auto bit_query = [&](ll b[], int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += b[idx];
        }
        return sum;
    };
    int w = lca(u, v);
    return bit_query(bit, in[u]) + bit_query(bit, in[v]) - 2 * bit_query(bit, in[w]);
}

ll get1(ll u, ll v) {
    auto bit_query = [&](ll b[], int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += b[idx];
        }
        return sum;
    };
    int w = lca(u, v);
    return bit_query(bit1, in[u]) + bit_query(bit1, in[v]) - 2 * bit_query(bit1, in[w]);
}

void dfs1(ll u, ll parent) {
	for (auto v : adj[u]) {
		if (v == parent) continue;
		f[v] += f[u];
		dfs1(v, u);
	}
}
void dfs(ll u, ll parent, ll h) {
    in[u] = ++timer;
    par[u][0] = parent;
    high[u] = h;
    sz[u] = 1;
    for (auto v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u, h + 1);
        sz[u] += sz[v];
    }
    out[u] = timer;
}

ll L[N], R[N], ans[N], kq[N], cnt[N];

bool cmp2(pii a, pii b) {
	return a.se < b.se;
}

void solve() {
	for (int i = 1; i <= q; i ++) {
		L[i] = 0, R[i] = m; ans[i] = -1;
	}
	sort(p + 1, p + 1 + m, cmp2);
	bool flag = 1;
	ll turn =0;
	while (flag) {
		turn ++ ;
		//cout << "turn: " << turn << endl;
		flag = 0;
		vector<ll> bucket[m + 2];
		memset(bit, 0, sizeof(bit));
        memset(bit1, 0, sizeof(bit1));

		for (int i = 1; i <= q; i ++) {
			if (L[i] <= R[i]) {
                flag = 1;
			    ll mid = (L[i] + R[i]) / 2;
			    bucket[mid].push_back(i);
			    //cout << "b " << mid << " " << i << " LR " << L[i] << " " << R[i] << " " << ans[i] << endl;
            }
		}
        if (!flag) break;

		for (int i = 0; i <= m; i ++) {
			if (i > 0) {
                ll edge_index = p[i].fi;
                ll child_node = canh[edge_index].v;
                ll weight = p[i].se;
			    update(child_node, weight);
			    //cout << "upd " << child_node << " " << weight << endl;
            }
			for (auto it : bucket[i]) {
				ll u = qr[it].s, v = qr[it].t;
				if (get(u, v) <= qr[it].y) {
					ans[it] = i;
					L[it] = i + 1;
					kq[it] = get1(u, v);
				}
				else {
					R[it] = i - 1;
				}
			}
		}
	}
	
	for (int i = 1; i <= q; i ++) {
		//cout << i << " " << ans[i] << " " << kq[i] << " " << cnt[i] << " " << qr[i].x << endl;
		ll dungvang = cnt[i] - kq[i]; // cai nay mini
		ll left = qr[i].x - dungvang;
		if (left < 0) {
			left = -1;
		}
		cout << left << endl;
	}
}

bool klinh;

signed main(void) {
	faster;
	
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i ++) {
		cin >> canh[i].u >> canh[i].v;
	}
	
	for (int i = 1; i <= m; i ++) {
		ll s, t;
		cin >> s >> t;
		p[i] = {s, t};
	}
	
	for (int i = 1; i <= n - 1; i ++) {
		ll u = canh[i].u, v = canh[i].v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	dfs(1, 0, 0);
    prepare();
	
	for (int i = 1; i < n; i++) {
        if(par[canh[i].u][0] == canh[i].v) {
            swap(canh[i].u, canh[i].v);
        }
    }
	
	for (int i = 1; i <= m; i ++) {
		ll s = p[i].fi;
		f[canh[s].v]++;
		//cout << canh[s].v << endl;
	}
	
	dfs1(1, 0);
	
	for (int i = 1; i <= q; i ++) {
		cin >> qr[i].s >> qr[i].t >> qr[i].x >> qr[i].y;
		cnt[i] = f[qr[i].s] + f[qr[i].t] - 2 * f[lca(qr[i].s, qr[i].t)];
	}
	
	solve();
	
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    return 0;
}

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