제출 #1252482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252482		giaminhha	Two Currencies (JOI23_currencies)	C++20	100 / 100	1070 ms	40996 KiB

currencies

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int, int> pii;
const int mod = 2147483647;
const int inf = 1e9 + 7;
const int N = 1e5 + 5;

int h[N], tin[N], tout[N], t = 0;
int up[N][20];
vector<int> adj[N];
void dfs(int u, int par){
    tin[u] = ++t;
    for(int v : adj[u]){
        if(v == par) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
    tout[u] = t;
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int diff = h[u] - h[v];
    for(int i = 18; i >= 0; i--){
        if(diff >= (1 << i)){
            diff -= (1 << i);
            u = up[u][i];
        }
    }
    if(u == v) return u;

    for(int i = 18; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

struct Fenwick{
    vector<ll> f; int n;
    Fenwick(int _n){
        n = _n;
        f.resize(n + 5, 0);
    }
    void update_point(int u, int val){
        for(; u < N; u += u&(-u)){
            f[u] += val;
        }
    }
    void update_range(int u, int v, ll val){
        update_point(u, val);
        update_point(v + 1, -val);
    }
    ll get(int u){
        ll ans = 0;
        for(; u > 0; u -= u&(-u)){
            ans += f[u];
        }
        return ans;
    }
};

bool is_ances(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
vector<int> bucket[N];
int leftb[N], rightb[N], ans[N];
pair<ll, int> p[N];
int S[N], T[N]; ll X[N], Y[N];
signed main(){
    fastio
    int n, m, q; cin >> n >> m >> q;
    vector<pii> edges;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        edges.pb({u, v});
    }
    for(int i = 1; i <= m; i++){
        int x; ll y; cin >> x >> y;
        p[i] = {y, x};  
    }
    h[1] = 0;
    dfs(1, 1);  
    for(int i = 0; i < edges.size(); i++){
        if(is_ances(edges[i].se, edges[i].fi)) swap(edges[i].fi, edges[i].se);
    }
    up[1][0] = 1;
    for(int i = 1; i <= 18; i++){
        for(int j = 1; j <= n; j++) up[j][i] = up[up[j][i - 1]][i - 1];
    }
    for(int i = 1; i <= q; i++){
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        leftb[i] = 0; rightb[i] = m;
        ans[i] = inf;
    }
    sort(p + 1, p + m + 1);
    
    while(true){
        
        bool ck = false;
        for(int i = 1; i <= q; i++){
            if(leftb[i] < rightb[i]){
                int mid = (leftb[i] + rightb[i] + 1) >> 1;
                bucket[mid].pb(i);
                ck = true;
            }
        }
        if(!ck) break;
        Fenwick cost_tree(N), count_tree(N);
        for(int i = 0; i <= m; i++){
            if(i > 0){
                int u = edges[p[i].se - 1].se;
                cost_tree.update_range(tin[u], tout[u], p[i].fi);
                count_tree.update_range(tin[u], tout[u], 1);
            }
            for(int idx : bucket[i]){
                ll gold_needed = count_tree.get(tin[S[idx]]) + count_tree.get(tin[T[idx]]) - 2 * count_tree.get(tin[lca(S[idx], T[idx])]);
                ll silver_needed = cost_tree.get(tin[S[idx]]) + cost_tree.get(tin[T[idx]]) - 2 * cost_tree.get(tin[lca(S[idx], T[idx])]);  
                if(silver_needed <= Y[idx]){
                    ans[idx] = gold_needed;
                    leftb[idx] = i;
                }
                else rightb[idx] = i - 1;
            }
            bucket[i].clear();
        }
    }
    Fenwick bit(N);
    for(int i = 1; i <= m; i++){
        int v = edges[p[i].se - 1].se;
        bit.update_range(tin[v], tout[v], 1);
    }
    for(int i = 1; i <= q; i++){
        if(ans[i] >= inf) ans[i] = 0;
        cout << max((ll)-1, X[i] - (bit.get(tin[S[i]]) + bit.get(tin[T[i]]) - 2 * bit.get(tin[lca(S[i], T[i])]) - ans[i])) << '\n';
    }
    return 0;
}

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