제출 #944643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944643		phoenix0423	Two Currencies (JOI23_currencies)	C++17	40 / 100	5039 ms	288624 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")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
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 head[maxn];
int cnt = 0;
int n, m, q;

void dfs(int pos, int prev){
    if(prev != -1) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
    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]);
    }
}

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){}
};
pll st[maxn * 4];

void upd(int pos, int val, int v = 1, int l = 0, int r = maxn - 1){
    st[v].f += val, st[v].s += (val > 0 ? 1 : -1);
    if(l == r){
        return;
    }
    int m = (l + r) / 2;
    if(pos <= m) upd(pos, val, v * 2, l, m);
    else upd(pos, val, v * 2 + 1, m + 1, r);
}
pll operator + (pll a, pll b){
    return pll(a.f + b.f, a.s + b.s);
}
pll qry(int l, int r, int v = 1, int L = 0, int R = maxn - 1){
    if(l > R || r < L) return {0, 0};
    if(l <= L && r >= R) return st[v];
    int m = (L + R) / 2;
    return qry(l, r, v * 2, L, m) + qry(l, r, v * 2 + 1, m + 1, R);
}
pll solve(int a, int b){
    pll ret = {0, 0};
    while(head[a] != head[b]){
        if(dep[head[a]] > dep[head[b]]) swap(a, b);
        ret = ret + qry(id[head[b]], id[b]);
        b = par[head[b]];
    }
    if(dep[a] > dep[b]) swap(a, b);
    ret = ret + qry(id[a] + 1, id[b]);
    return ret;
}
pll lok[maxn]; // 剛好可以 max. amount of gold coins 
pll bad[maxn]; // 剛好不行

void bs(vector<pll> a, vector<info> rng, int l, int r, vector<pll> ax){
    if(!rng.size()) return;
    // cout<<"bs : "<<l<<" "<<r<<"\n";
    if(l + 1 == r || ! a.size()){
        for(auto [s, t, x, y, id] : rng){
            // auto [cnt, ttl] = solve(s, t);
            lok[id] = solve(s, t);
            continue;
            // cout<<"end "<<id<<" : "<<l<<", ";
            // cout<<cnt<<" "<<ttl<<"\n";
            // if(cnt > y) ans[id] = -INF * INF;
            // else ans[id] += ttl;
        }
        for(auto [c, p] : ax){
            auto [x, y] = road[p];
            if(dep[x] < dep[y]) swap(x, y);
            upd(id[x], c);
        }
        for(auto [s, t, x, y, id] : rng){
            bad[id] = solve(s, t);
            continue;
        }
        for(auto [c, p] : ax){
            auto [x, y] = road[p];
            if(dep[x] < dep[y]) swap(x, y);
            upd(id[x], -c);
        }
        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);
            // cout<<"cur : "<<x<<" "<<y<<" "<<p<<"\n";
            upd(id[x], c);
        }
        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);
        // cout<<"get : "<<id<<" "<<x<<" "<<cnt<<" "<<ttl<<"\n";
        if(y >= cnt) r2.pb(info(s, t, x, y, id));
        else r1.pb(info(s, t, x, y, id));
    }
    bs(a2, r2, m, r, ax);
    for(auto [c, p] : a1){
        auto [x, y] = road[p];
        if(dep[x] < dep[y]) swap(x, y);
        upd(id[x], -c);
    }
    bs(a1, r1, l, m, nax);
}
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, empt);
    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);
        upd(id[b], 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 < n; i++) cout<<head[i]<<" "<<id[i]<<"\n";
    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: 0 / 28
• Subtask 3: 30 / 30
• Subtask 4: 0 / 32