Submission #939883

#	Time	Username	Problem	Language	Result	Execution time	Memory
939883		nextgenxing	Two Currencies (JOI23_currencies)	C++14	30 / 100	3707 ms	124796 KiB

currencies

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
const int MAX_N = 1e5+5;
const ll INF = 1e18;

int n, m, q, t, cnt;
int idx[MAX_N], lst[MAX_N], sz[MAX_N], dep[MAX_N], anc[MAX_N][20], rt[MAX_N], ch[50*MAX_N][2];
ll sm[50*MAX_N], num[50*MAX_N];
vector<ll> nums[MAX_N];
vector<pii> adj[MAX_N];

int upd(int x, ll l, ll r, ll v){
    ll x2 = ++cnt, m = (l+r)/2ll;
    if(l == r){
        sm[x2] = sm[x]+v;
        num[x2] = num[x]+1;
        return x2;
    }
    if(v <= m){
        ch[x2][0] = upd(ch[x][0], l, m, v);
        ch[x2][1] = ch[x][1];
    } else{
        ch[x2][0] = ch[x][0];
        ch[x2][1] = upd(ch[x][1], m+1ll, r, v);
    }
    sm[x2] = sm[ch[x2][0]]+sm[ch[x2][1]];
    num[x2] = num[ch[x2][0]]+num[ch[x2][1]];
    return x2;
}

ll qry1(int x, ll l, ll r, ll ql, ll qr){
    if(!x || ql > r || qr < l) return 0;
    if(ql <= l && qr >= r) return sm[x];
    ll m = (l+r)/2ll;
    return qry1(ch[x][0], l, m, ql, qr)+qry1(ch[x][1], m+1, r, ql, qr);
}

ll qry2(int x, ll l, ll r, ll ql, ll qr){
    if(!x || ql > r || qr < l) return 0;
    if(ql <= l && qr >= r) return num[x];
    ll m = (l+r)/2ll;
    return qry2(ch[x][0], l, m, ql, qr)+qry2(ch[x][1], m+1, r, ql, qr);
}

int dfs1(int curr, int par){
    sz[curr] = 1;
    vector<pii> nadj;
    for(auto x : adj[curr]){
        if(x.ff == par) continue;
        nadj.push_back(x);
        dep[x.ff] = dep[curr]+1;
        anc[x.ff][0] = curr;
        sz[curr] += dfs1(x.ff, curr);
    }
    adj[curr] = nadj;
    for(auto &x : adj[curr])
        if(sz[x.ff] > sz[adj[curr][0].ff])
            swap(x, adj[curr][0]);
    return sz[curr];
}

void dfs2(int curr){
    idx[curr] = t++;
    for(auto x : adj[curr]){
        if(x == adj[curr][0]) lst[x.ff] = lst[curr];
        else lst[x.ff] = x.ff;
        rt[t] = rt[t-1];
        for(auto y : nums[x.ss])
            rt[t] = upd(rt[t], 0, 1e9, y);
        dfs2(x.ff);
    }
}

int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    F0Rd(i, 20) if(dep[a]+(1 << i) <= dep[b])
        b = anc[b][i];
    if(a == b) return a;
    F0Rd(i, 20) if(anc[a][i] != anc[b][i])
        a = anc[a][i], b = anc[b][i];
    return anc[a][0];
}

pair<pii, ll> solve(int a, int b, ll x){ // number of things > x, number of things = x, sum of things < x
    pair<pii, ll> ans = {{0, 0}, 0};
    int c = lca(a, b);
    F0R(i, 2){
        while(a != c){
            int y = lst[a]; if(dep[y] < c) y = c;
            ans.ff.ff += qry2(rt[idx[a]], 0, 1e9, x+1ll, 1e9);
            ans.ff.ff -= qry2(rt[idx[y]-(y != c)], 0, 1e9, x+1ll, 1e9);
            ans.ff.ss += qry2(rt[idx[a]], 0, 1e9, x, x);
            ans.ff.ss -= qry2(rt[idx[y]-(y != c)], 0, 1e9, x, x);
            ans.ss += qry1(rt[idx[a]], 0, 1e9, 0, x-1);
            ans.ss -= qry1(rt[idx[y]-(y != c)], 0, 1e9, 0, x-1);
            if(y != c) a = anc[y][0];
            else a = y;
        }
        swap(a, b);
    }
    return ans;
}

int main(int argc, const char * argv[]){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> m >> q;
    F0R(i, n-1){
        int a, b; cin >> a >> b; a--, b--;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    F0R(i, m){
        int a, b; cin >> a >> b; a--;
        nums[a].push_back(b);
    }
    dfs1(0, -1);
    FOR(x, 1, 20) F0R(i, n)
        anc[i][x] = anc[anc[i][x-1]][x-1];
    dfs2(0);
    F0R(i, q){
        ll s, t, x, y; cin >> s >> t >> x >> y; s--, t--;
        ll l = 0, r = min(y+1ll, (ll) 1e9);
        while(l+1 < r){
            ll mid = (l+r)/2ll;
            if(solve(s, t, mid).ss <= y) l = mid;
            else r = mid; 
        }
        pair<pll, ll> z = solve(s, t, l);
        pll ans = {z.ff.ff, z.ss};
        if(z.ff.ss*l+z.ss <= y) ans.ss += z.ff.ss;
        else ans.ss += l*((y-z.ss)/l), ans.ff += z.ff.ss-(y-z.ss)/l;
        if(ans.ff > x) cout << "-1\n";
        else cout << x-ans.ff << '\n';
    }
    return 0;
}

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