Submission #990985

#	Time	Username	Problem	Language	Result	Execution time	Memory
990985		Pacybwoah	Two Currencies (JOI23_currencies)	C++17	100 / 100	1258 ms	46456 KiB

currencies

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;
int n, m, q, sz;
vector<vector<int>> pts, graph;
vector<pair<int, int>> edges;
vector<ll> cp;
struct Query{
    int s, t;
    ll x, y;
    int id;
    Query(int _s, int _t, ll _x, ll _y, int _id){
        s = _s, t = _t, x = _x, y = _y, id = _id;
    }
};
vector<Query> queries;
vector<ll> ans;
vector<vector<int>> anc;
vector<int> in, out, dep;
int cnt = 0;
void dfs(int node, int parent){
    in[node] = ++cnt;
    anc[0][node] = parent;
    dep[node] = dep[parent] + 1;
    for(auto &x: graph[node]){
        if(x == parent) continue;
        dfs(x, node);
    }
    out[node] = cnt;
}
vector<ll> bit, bit2;
void modify(int pos, ll num){
    while(pos <= n){
        bit[pos] += num;
        pos += (pos & -pos);
    }
}
ll query(int pos){
    ll ans = 0;
    while(pos > 0){
        ans += bit[pos];
        pos -= (pos & -pos);
    }
    return ans;
}
void modify2(int pos, ll num){
    while(pos <= n){
        bit2[pos] += num;
        pos += (pos & -pos);
    }
}
ll query2(int pos){
    ll ans = 0;
    while(pos > 0){
        ans += bit2[pos];
        pos -= (pos & -pos);
    }
    return ans;
}
int lca(int a, int b){
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 0; i < 18; i++){
        if((dep[a] - dep[b]) & (1 << i)) a = anc[i][a];
    }
    for(int i = 17; i >= 0; i--){
        if(anc[i][a] != anc[i][b]){
            a = anc[i][a];
            b = anc[i][b];
        }
    }
    if(a != b){
        a = anc[0][a];
        b = anc[0][b];
    }
    return a;
}
void add(int l, int r){
    for(int i = l; i <= r; i++){
        ll val = cp[i - 1];
        for(auto &x: pts[i]){
            auto [a, b] = edges[x];
            if(dep[a] < dep[b]) swap(a, b);
            modify(in[a], val);
            if(out[a] < n) modify(out[a] + 1, -val);
            modify2(in[a], -1);
            if(out[a] < n) modify2(out[a] + 1, 1);
        }
    }
}
void rollback(int l, int r){
    for(int i = l; i <= r; i++){
        ll val = cp[i - 1];
        for(auto &x: pts[i]){
            auto [a, b] = edges[x];
            if(dep[a] < dep[b]) swap(a, b);
            modify(in[a], -val);
            if(out[a] < n) modify(out[a] + 1, val);
            modify2(in[a], 1);
            if(out[a] < n) modify2(out[a] + 1, -1); 
        }
    }
}
void f(int l, int r, vector<Query>& queries){
    if(l == r){
        add(l, r);
        for(auto &[s, t, x, y, id]: queries){
            ll ag = query(in[s]) + query(in[t]) - 2 * query(in[lca(s, t)]), au = query2(in[s]) + query2(in[t]) - 2 * query2(in[lca(s, t)]);
            if(ag <= y && au <= x) ans[id] = x - au;
            else ans[id] = -1;
            //cout << id << " " << ag << " " << au << "\n";
        }
        rollback(l, r);
        if(l == 1){
            for(auto &[s, t, x, y, id]: queries){
                ll ag = query(in[s]) + query(in[t]) - 2 * query(in[lca(s, t)]), au = query2(in[s]) + query2(in[t]) - 2 * query2(in[lca(s, t)]);
                if(ans[id] == -1){
                    if(au <= x) ans[id] = x - au;
                }
            }
        }
        return;
    }
    int mid = ((l + r) >> 1) + 1;
    add(l, mid);
    vector<Query> ql, qr;
    for(auto &[s, t, x, y, id]: queries){
        ll ag = query(in[s]) + query(in[t]) - 2 * query(in[lca(s, t)]), au = query2(in[s]) + query2(in[t]) - 2 * query2(in[lca(s, t)]);
        if(ag > y) ql.emplace_back(s, t, x, y, id);
        else qr.emplace_back(s, t, x, y, id);
        //cout << id << " " << mid << " " << ag << " " << au << "\n";
    }
    vector<Query>().swap(queries);
    rollback(mid, mid);
    f(mid, r, qr);
    rollback(l, mid - 1);
    f(l, mid - 1, ql);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    graph.resize(n + 1);
    pts.resize(m + 1);
    edges.resize(n);
    ans.resize(q);
    anc.resize(18, vector<int>(n + 1));
    in.resize(n + 1);
    out.resize(n + 1);
    dep.resize(n + 1);
    bit2.resize(n + 1);
    bit.resize(n + 1);
    ll a, b;
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        edges[i] = make_pair(a, b);
    }
    vector<pair<int, ll>> chktmp;
    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        chktmp.emplace_back(a, b);
        cp.push_back(b);
    }
    sort(cp.begin(), cp.end());
    vector<int> cntt(m + 1);
    for(auto &[id, val]: chktmp){
        val = lower_bound(cp.begin(), cp.end(), val) - cp.begin() + 1;
        cntt[val]++;
        val += cntt[val] - 1;
        pts[val].push_back(id);
    }
    sz = cp.size();
    for(int i = 0; i < q; i++){
        int s, t;
        ll x, y;
        cin >> s >> t >> x >> y;
        queries.emplace_back(s, t, x, y, i);
    }
    dfs(1, 1);
    for(int i = 1; i < 18; i++){
        for(int j = 1; j <= n; j++){
            anc[i][j] = anc[i - 1][anc[i - 1][j]];
        }
    }
    for(int i = 1; i <= sz; i++){
        for(auto &x: pts[i]){
            auto [a, b] = edges[x];
            if(dep[a] < dep[b]) swap(a, b);
            modify2(in[a], 1);
            if(out[a] < n) modify2(out[a] + 1, -1);
        }
    }
    f(1, sz, queries);
    for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
// g++ -std=gnu++20 pA.cpp -o run -Wall -Wextra -fsanitize=undefined -fsanitize=address

Compilation message (stderr)

currencies.cpp: In function 'void f(int, int, std::vector<Query>&)':
currencies.cpp:118:20: warning: unused variable 'ag' [-Wunused-variable]
  118 |                 ll ag = query(in[s]) + query(in[t]) - 2 * query(in[lca(s, t)]), au = query2(in[s]) + query2(in[t]) - 2 * query2(in[lca(s, t)]);
      |                    ^~
currencies.cpp:130:73: warning: unused variable 'au' [-Wunused-variable]
  130 |         ll ag = query(in[s]) + query(in[t]) - 2 * query(in[lca(s, t)]), au = query2(in[s]) + query2(in[t]) - 2 * query2(in[lca(s, t)]);
      |                                                                         ^~

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