제출 #1181694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181694		Gray	Two Currencies (JOI23_currencies)	C++20	100 / 100	4681 ms	112140 KiB

currencies

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD 998244353

struct SegTree{
    vector<vector<ll>> t;
    vector<vector<ll>> tpref;
    ll sz, rsz;
    void init(ll N){
        sz=N*4; rsz=N;
        tpref.resize(sz); t.resize(sz);
    }
    void build(ll tl, ll tr, ll v, vector<vector<ll>> &a){
        if (tl==tr){
            t[v] = a[tl];
            tpref[v]=a[tl];
            for (ll i=1; i<(ll)tpref[v].size(); i++) tpref[v][i]+=tpref[v][i-1];
        }else{
            ll tm = (tl+tr)/2;
            build(tl, tm, v*2, a);
            build(tm+1, tr, v*2+1, a);
            merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(), back_inserter(t[v]));
            tpref[v].resize(t[v].size());
            for (ll i=0; i<(ll)t[v].size(); i++){
                tpref[v][i]=(i?tpref[v][i-1]:0ll)+t[v][i];
            }
        }
    }

    pair<ll, ll> query(ll tl, ll tr, ll v, ll l, ll r, ll x){
        if (tl==l and tr==r){
            ll ind = upper_bound(t[v].begin(), t[v].end(), x)-t[v].begin()-1;
            pair<ll, ll> ret = {0, 0};
            if (ind>=0){
                ret=mp(ind+1ll, tpref[v][ind]);
            }
            return ret;
        }else if (l>r) return {0, 0};
        else{
            ll tm = (tl+tr)/2;
            pair<ll, ll> resl = query(tl, tm, v*2, l, min(r, tm), x);
            pair<ll, ll> resr = query(tm+1, tr, v*2+1, max(l, tm+1), r, x);
            return {resl.ff+resr.ff, resl.ss+resr.ss};
        }
    }

    void build(vector<vector<ll>> &a){
        build(0, rsz-1, 1, a);
    }

    pair<ll, ll> query(ll l, ll r, ll x){
        // cout << l << " - " << r << " - " << x << " -> ";
        if (l>r) swap(l, r);
        pair<ll, ll> ret=query(0, rsz-1, 1, l, r, x);
        // cout << ret.ff << " " << ret.ss << ln;
        return ret;
    }
};

struct edge{
    ll u, v; vector<ll> control;
};

struct HLD{
    ll n; vector<edge> e;
    vector<vector<ll>> A;
    vector<ll> sz, level;
    vector<ll> eid, nxt;
    vector<vector<ll>> euler, bin /*just in case*/;
    SegTree ds;
    void dfs1(ll u, ll p, ll clev){
        bin[u][0]=p; level[u]=clev; sz[u]=1; ll mxsz=0;
        for (ll i=1; i<20; i++) bin[u][i]=bin[bin[u][i-1]][i-1];
        for (auto &i:A[u]){
            ll v = e[i].u^e[i].v^u;
            if (v==p) continue;
            dfs1(v, u, clev+1); sz[u]+=sz[v];
            if (mxsz<sz[v]) swap(i, A[u][0]), mxsz=sz[v];
        }
    }

    void dfs2(ll u, ll p){
        bool first=1;
        for (auto i:A[u]){
            ll v = e[i].u^e[i].v^u;
            if (v==p) continue;
            eid[v]=euler.size();
            euler.push_back(e[i].control);
            if (first) nxt[v]=nxt[u];
            else nxt[v]=v;
            dfs2(v, u); first=0;
        }
    }

    HLD(ll N, vector<edge> &_e){
        n=N; e=_e; A.resize(n+1);
        sz.resize(n+1); level.resize(n+1);
        nxt.resize(n+1); bin.resize(n+1, vector<ll>(20));
        eid.resize(n+1);
        for (ll i=0; i<n-1; i++){
            A[e[i].u].push_back(i); A[e[i].v].push_back(i);
        }
        nxt[1]=1; euler.push_back(vector<ll>());
        dfs1(1, 1, 1); dfs2(1, 1); ds.init(N);
        ds.build(euler);
        // for (ll i=1; i<=n; i++) cout << level[i] << " ";
        // cout<<endl;
    }

    pair<ll, ll> queryLOW(ll u, ll v, ll c){
        // cout << "ENT" << u << " - " << v << " - " << c << endl;
        if (u==v) return {0, 0};
        pair<ll, ll> res = {0, 0};
        while (nxt[u]!=nxt[v]){
            // cout << u << " - " << v << " <-> ";
            if (level[nxt[u]]<level[nxt[v]]) swap(u, v);
            pair<ll, ll> ret=ds.query(eid[u], eid[nxt[u]], c);
            res.ff+=ret.ff; res.ss+=ret.ss;
            u=bin[nxt[u]][0];
        }
        // cout << u << " - " << v << endl;
        // cout << "CAME" << endl;
        if (u!=v){
            if (level[u]<level[v]) swap(u, v);
            ll jump = level[u]-level[v]-1;
            ll tu = u;
            for (ll i=0; i<20; i++){
                if (jump&(1ull<<i)){
                    tu=bin[tu][i];
                }
            }
            pair<ll, ll> ret=ds.query(eid[u], eid[tu], c);
            res.ff+=ret.ff; res.ss+=ret.ss;
        }
        // cout << "DONE -> " << res.ff << " - " << res.ss << endl;
        return res;
    }

    ll query(ll u, ll v, ll s, ll g){
        ll l=0, r=s+2;
        while (l+1<r){
            ll mid = (l+r)/2;
            if (queryLOW(u, v, mid).ss<=s) l=mid;
            else r=mid;
        }
        pair<ll, ll> data = queryLOW(u, v, l);
        ll total = queryLOW(u, v, 2e9).ff;
        total-=data.ff; s-=data.ss; total-=s/(l+1);
        return max(-1ll, g-total);
    }
};


void solve(){
    ll n, m, q; cin >> n >> m >> q;
    vector<edge> e(n-1);
    for (ll i=0; i<n-1; i++){
        cin >> e[i].u >> e[i].v;
    }
    for (ll i=0; i<m; i++){
        ll id, x; cin >> id >> x;
        e[id-1].control.push_back(x);
    }
    for (ll i=0; i<n-1; i++){
        sort(e[i].control.begin(), e[i].control.end());
    }
    HLD tr(n, e);
    // return;
    while (q--){
        ll u, v, g, s; cin >> u >> v >> g >> s;
        cout << tr.query(u, v, s, g) << ln;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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