Submission #1098655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098655		flyingkite	Two Currencies (JOI23_currencies)	C++17	100 / 100	4618 ms	77644 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
#define int long long
const ll N = 1e5 + 100;
const ll inf = 1e18;
const ll block = 350;
ll n,m,q,timer=0;
vector<ll>adj[N];
ll tin[N], tout[N], cur[N], up[N][20], d[N], ps[N], ans[N];
pll e[N];
vector<pll>cost;
struct queries{ll u,v,x,y;} h[N];
struct value{ll ans,f,s;} res[N];
struct ccjv{ll s,t,x,y,l,r,idx;};
vector<ccjv>g;
map<ll,vector<ll>>mp, upd;
struct Fen{
    vector<ll>bit1, bit2;
    void init(ll _n){
		bit1.clear(); bit2.clear();
		bit1.resize(_n + 10), bit2.resize(_n + 10);
	};
    void updatePoint(vector<ll>& b, int u, ll v) {
        int idx = u;
        while (idx <= n) {
            b[idx] = (b[idx] + v);
            idx += (idx & (-idx));
        }
    }
    void updateRange(int l, int r, ll v) {
        updatePoint(bit1, l, ((n - l + 1) * v));
        updatePoint(bit1, r + 1, (-(n - r) * v));
        updatePoint(bit2, l, v);
        updatePoint(bit2, r + 1, -v);
    }
    ll getSum(vector<ll>& b, ll u) {
        ll idx = u, ans = 0;
        while (idx > 0) {
            ans = (ans + b[idx]);
            idx -= (idx & (-idx));
        }
        return ans;
    }
    ll prefixSum(ll u) {
        ll x = (getSum(bit1, u) - (getSum(bit2, u) * (n - u)));
        return x;
    }
    ll rangeSum(int l, int r) {
        ll x = (prefixSum(r) - prefixSum(l - 1));
        return x;
    }
} ft, cnt;
void pre_dfs(ll u, ll par){
	tin[u] = ++timer;
	for(auto v : adj[u]){
		if(v == par) continue;
		up[v][0] = u;
        for(int i = 1; i <= 19;i++) up[v][i] = up[up[v][i-1]][i-1];
        d[v] = d[u] + 1;
		pre_dfs(v, u);
	}
	tout[u] = timer;
}
void re_dfs(ll u, ll par){
	for(auto v : adj[u]){
		if(v == par) continue;
		ps[v] += ps[u];
		re_dfs(v, u);
	}
}
ll lca(ll u, ll v){
    if(d[u] != d[v]){
        if(d[u] < d[v]) swap(u, v);
        ll k = d[u] - d[v];
        for(int i = 19; i >= 0;i--) if(k & (1 << i)) u = up[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0;i--) if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
    return up[u][0];
}
void calc(){
	if(!g.size()) return;
	sort(all(g), [&](const ccjv &a, const ccjv&b){
		return (a.l + a.r) / 2 < (b.l + b.r) / 2;
	});
	ll j = 0;
	ft.init(n); cnt.init(n);
	vector<ccjv>cur;
	for(auto tmp : g){
		ll u = tmp.s, v = tmp.t, x = tmp.x, y = tmp.y, l = tmp.l, r = tmp.r, idx = tmp.idx, p = lca(u, v), mid = (l + r) / 2;
		while(j < cost.size() && cost[j].F <= mid){
			ll i = cost[j].S;
			ft.updateRange(tin[e[i].F], tout[e[i].F], cost[j].F);
			cnt.updateRange(tin[e[i].F], tout[e[i].F], 1);
			j++;
		}
		ll w = ft.rangeSum(tin[u], tin[u]) + ft.rangeSum(tin[v], tin[v]) - 2 * ft.rangeSum(tin[p], tin[p]);
		if(w <= y){
			res[idx] = {mid, cnt.rangeSum(tin[u], tin[u]) + cnt.rangeSum(tin[v], tin[v]) - 2 * cnt.rangeSum(tin[p], tin[p]), w};
			if(mid + 1 <= r) cur.pb({u,v,x,y,mid+1,r,idx});
		}
		else if(l + 1 <= mid) cur.pb({u,v,x,y,l,mid-1,idx});
	}	
	swap(cur, g);
}
void to_thic_cau(){
	cin >> n >> m >> q;
	for(int i = 1; i <= n - 1;i++){
		ll u,v; cin >> u >> v;
		e[i] = {u, v};
		adj[u].pb(v); adj[v].pb(u);
	}
	pre_dfs(1, 0);
	for(int i = 1; i <= m;i++){
		ll idx,c; cin >> idx >> c;
		if(up[e[idx].F][0] != e[idx].S) swap(e[idx].F, e[idx].S);
		ps[e[idx].F]++;
		cost.pb({c, idx});
		upd[c].pb(idx);
	}
	re_dfs(1, 0);
	sort(all(cost));
	for(int i = 1; i <= q;i++){
		ll s,t,x,y; cin >> s >> t >> x >> y;
		g.pb({s,t,x,y,0,(ll)1e9,i});
		h[i] = {s,t,x,y};
	}
	for(int i = 1; i <= q;i++) res[i].ans = -1;
	for(int i = 1; i <= 30;i++) calc();
	vector<ll>order;
	for(int i = 1; i <= q;i++){
		if(res[i].ans == -1) continue;
		order.pb(res[i].ans + 1);
		mp[res[i].ans + 1].pb(i);
	}
	//for(int i = 1; i <= n;i++) cout << res[i].s << ' ';
	//cout << '\n';
	sort(all(order)); order.erase(unique(all(order)), order.end());
	cnt.init(n);
	for(auto tmp : order){
		for(auto i : upd[tmp]) cnt.updateRange(tin[e[i].F], tout[e[i].F], 1);
		for(auto i : mp[tmp]){
			ll u = h[i].u, v = h[i].v, x = h[i].x, y = h[i].y;
			ll p = lca(u, v);
			ll rem = cnt.rangeSum(tin[u], tin[u]) + cnt.rangeSum(tin[v], tin[v]) - 2 * cnt.rangeSum(tin[p], tin[p]);
			rem = min(rem, (y - res[i].s) / tmp);
			ll freq = res[i].f + rem;
			ll len = ps[u] + ps[v] - 2 * ps[lca(u, v)];
			len -= freq;
			if(len > x) ans[i] = -1;
			else ans[i] = x - len;
		}
		for(auto i : upd[tmp]) cnt.updateRange(tin[e[i].F], tout[e[i].F], -1);
	}
	for(int i = 1; i <= q;i++) cout << ans[i] << '\n';
	cout << '\n';
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Compilation message (stderr)

currencies.cpp: In function 'void calc()':
currencies.cpp:98:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   while(j < cost.size() && cost[j].F <= mid){
      |         ~~^~~~~~~~~~~~~

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