Submission #1177199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177199		mactoddlover	Two Currencies (JOI23_currencies)	C++17	100 / 100	1662 ms	45308 KiB

currencies

#include<bits/stdc++.h>

#define pii pair<int,int>
#define fi first
#define se second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)(v).size()

#define endl "\n"
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;

void fastIO(){
    ios_base::sync_with_stdio(NULL); cin.tie(0);
#ifdef LOCAL
    freopen("task.INP", "r", stdin);
    freopen("task.OUT", "w", stdout);
#endif // LOCAL
}

const int MAX = 2e5 + 5;
const int lg = 16;

struct FenwickTree{
    int n;
    vector<ll> bit;

    FenwickTree(int n) : n(n), bit(n + 5, 0) {}

    void update(int idx, ll v){
        for(;idx <= n; idx += (idx & (-idx))) bit[idx] += v;
    }

    ll get(int idx){ll res = 0;
        for(;idx; idx -= (idx & (-idx))) res += bit[idx];
        return res;
    }

    void reset(){
        for(int i = 1; i <= n; i++) bit[i] = 0;
    }
};

int n, m, q;
int eu[MAX], ev[MAX];
vector<int> adj[MAX];
pii tax[MAX];
int h[MAX];
int par[MAX][lg+1];
int tin[MAX], tout[MAX], timer;
pair<ll, ll> query[MAX], have[MAX];
ll ans[MAX];

void dfs(int u){
    tin[u] = ++timer;
    for(int v : adj[u]) if(v != par[u][0]){
        h[v] = h[u] + 1;
        par[v][0] = u;
        for(int j = 1; j <= lg; j++) par[v][j] = par[par[v][j-1]][j-1];
        dfs(v);
    }
    tout[u] = timer;
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);

    for(int j = lg; j >= 0; j--) if(h[u] - (1 << j) >= h[v]){
        u = par[u][j];
    }

    if(u == v) return u;

    for(int j = lg; j >= 0; j--){
        if(par[u][j] != par[v][j]){
            u = par[u][j];
            v = par[v][j];
        }
    }

    return par[u][0];
}

int l[MAX], r[MAX];
vector<int> candidates[MAX];

signed main(){
    fastIO();

    cin >> n >> m >> q;

    for(int i = 1; i < n; i++){
        cin >> eu[i] >> ev[i];
        adj[eu[i]].push_back(ev[i]);
        adj[ev[i]].push_back(eu[i]);
    }

    for(int i = 1; i <= m; i++){
        cin >> tax[i].se >> tax[i].fi;
    }

    for(int i = 1; i <= q; i++){
        cin >> query[i].fi >> query[i].se >> have[i].fi >> have[i].se;
        l[i] = 0;
        r[i] = m;
        ans[i] = -1;
    }

    dfs(1);

    for(int i = 1; i < n; i++){
        if(h[eu[i]] > h[ev[i]]) swap(eu[i], ev[i]);
    }

    sort(tax + 1, tax + 1 + m);

    for(int i = 1; i <= m; i++) swap(tax[i].fi, tax[i].se);

    FenwickTree bit(n), cnt(n);

    while(true){
        bool any = false;
        for(int i = 1; i <= q; i++){
            if(l[i] > r[i]) continue;
            candidates[l[i] + r[i] >> 1].push_back(i);
            any = true;
        }
        if(!any) break;
        for(int i = 1; i <= m; i++){
            int id = tax[i].fi;
            cnt.update(tin[ev[id]], 1);
            cnt.update(tout[ev[id]] + 1, -1);
        }
        for(int i = 0; i <= m; i++){
            if(i){
                int id = tax[i].fi;
                int cost = tax[i].se;
                bit.update(tin[ev[id]], +cost);
                bit.update(tout[ev[id]] + 1, -cost);
                cnt.update(tin[ev[id]], -1);
                cnt.update(tout[ev[id]] + 1, +1);
            }

            auto get_dist = [&](int u, int v) -> ll{
                return bit.get(tin[u]) + bit.get(tin[v]) - 2LL*bit.get(tin[lca(u,v)]);
            };

            auto get_cnt = [&](int u, int v) -> ll{
                return cnt.get(tin[u]) + cnt.get(tin[v]) - 2LL*cnt.get(tin[lca(u,v)]);
            };

            while(sz(candidates[i])){
                int id = candidates[i].back();
                candidates[i].pop_back();
                if(get_dist(query[id].fi, query[id].se) <= have[id].se){
                    ans[id] = get_cnt(query[id].fi, query[id].se);
                    l[id] = i + 1;
                }
                else r[id] = i - 1;
            }
        }
        bit.reset();
        cnt.reset();
    }

    for(int i = 1; i <= q; i++){
        int res = ans[i];
        if(res != -1) res = max(-1LL, have[i].fi - ans[i]);
        cout << res << endl;
    }
}

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