Submission #944673

#	Time	Username	Problem	Language	Result	Execution time	Memory
944673		phoenix0423	Two Currencies (JOI23_currencies)	C++17	100 / 100	1526 ms	421356 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e9 + 7;
vector<int> adj[maxn];
pll road[maxn];
int sz[maxn], dep[maxn], id[maxn], loc[maxn], par[maxn];
int in[maxn], out[maxn];
int head[maxn];
int cnt = 0, dfn = 0;
int n, m, q;

pll operator + (pll a, pll b){
    return pll(a.f + b.f, a.s + b.s);
}
pll operator - (pll a, pll b){
    return pll(a.f - b.f, a.s - b.s);
}
void operator += (pll &a, pll b){
    a.f += b.f, a.s += b.s;
}
struct BITree{
    pll BIT[maxn * 2];
    void upd(int pos, pll val){
        while(pos < maxn * 2){
            BIT[pos] += val;
            pos += lowbit(pos);
        }
    }
    pll qry(int pos){
        pll ret = {0, 0};
        while(pos > 0){
            ret += BIT[pos];
            pos -= lowbit(pos);
        }
        return ret;
    }
} st;

void dfs(int pos, int prev){
    if(prev != -1) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
    in[pos] = ++dfn;
    sz[pos] = 1;
    for(auto &x : adj[pos]){
        dep[x] = dep[pos] + 1;
        par[x] = pos;
        dfs(x, pos);
        if(sz[x] > sz[adj[pos][0]]) swap(x, adj[pos][0]);
    }
    out[pos] = ++dfn;
}

void decompose(int pos, int h){
    head[pos] = h;
    // id[pos] = ++cnt, loc[cnt] = pos;
    for(auto x : adj[pos]){
        if(x == adj[pos][0]) decompose(x, h);
        else decompose(x, x);
    }
}

struct info{
    int s, t, x, y, id;
    info(){}
    info(int _s, int _t, int _x, int _y, int _id) : s(_s), t(_t), x(_x), y(_y), id(_id){}
};

int lca(int a, int b){
    while(head[a] != head[b]){
        if(dep[head[a]] > dep[head[b]]) swap(a, b);
        b = par[head[b]];
    }
    if(dep[a] > dep[b]) swap(a, b);
    return a;
}
pll solve(int s, int t){
    int lc = lca(s, t);
    return st.qry(in[s]) + st.qry(in[t]) - st.qry(in[lc]) - st.qry(in[lc]);
}
pll lok[maxn]; // 剛好可以 max. amount of gold coins 
pll bad[maxn]; // 剛好不行

void bs(vector<pll> a, vector<info> rng, int l, int r){
    if(!rng.size()) return;
    if(l + 1 == r || !a.size()){
        for(auto [s, t, x, y, id] : rng){
            lok[id] = solve(s, t);
        }
        return;
    }
    int m = (l + r) / 2;
    vector<pll> a1, a2, nax;    
    for(auto [c, p] : a){
        auto [x, y] = road[p];
        if(dep[x] < dep[y]) swap(x, y);
        if(c > m) a2.eb(c, p);
        else{
            a1.eb(c, p);
            st.upd(in[x], {c, 1});
            st.upd(out[x], {-c, -1});
        }
        if(c == m) nax.eb(c, p);
    }
    vector<info> r1, r2;
    for(auto [s, t, x, y, id] : rng){
        auto [cnt, ttl] = solve(s, t);
        if(y >= cnt) r2.pb(info(s, t, x, y, id));
        else bad[id] = {cnt, ttl}, r1.pb(info(s, t, x, y, id));
    }
    bs(a2, r2, m, r);
    for(auto [c, p] : a1){
        auto [x, y] = road[p];
        if(dep[x] < dep[y]) swap(x, y);
        st.upd(in[x], {-c, -1});
        st.upd(out[x], {c, 1});
    }
    bs(a1, r1, l, m);
}
int ans[maxn];

signed main(void){
    fastio;
    cin>>n>>m>>q;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
        road[i] = {a, b};
    }
    vector<pll> a(m);
    for(int i = 0; i < m; i++){
        cin>>a[i].s>>a[i].f;
        a[i].s--;
    }
    sort(a.begin(), a.end());
    vector<info> qry;
    for(int i = 0; i < q; i++){
        int s, t, x, y;
        cin>>s>>t>>x>>y;
        s--, t--;
        qry.pb(info(s, t, x, y, i));
    }
    dfs(0, -1);
    decompose(0, 0);
    vector<pll> empt;
    bs(a, qry, 0, INF);
    for(int i = 0; i < m; i++){
        auto [c, p] = a[i];
        auto [b, d] = road[p];
        if(dep[b] < dep[d]) swap(b, d);
        st.upd(in[b], {0, 1});
        st.upd(out[b], {0, -1});
    }
    for(int i = 0; i < q; i++){
        auto [s, t, x, y, id] = qry[i];
        auto [c1, t1] = lok[i];
        auto [c2, t2] = bad[i];
        if(t2 <= t1){
            ans[i] = x + t1 - solve(s, t).s;
            continue;
        }
        int cnt = (c2 - c1) / (t2 - t1);
        int canuse = (y - c1) / cnt;
        ans[i] += x + t1 + canuse - solve(s, t).s;
    }
    for(int i = 0; i < q; i++){
        cout<<(ans[i] < 0 ? -1 : ans[i])<<"\n";
    }
}  
/*
4 5 2
1 2
2 3
3 4
1 5
2 6
3 7
*/

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