Submission #1247670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247670		raphaeltfa	Two Currencies (JOI23_currencies)	C++20	100 / 100	622 ms	45772 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long

using namespace std;

const int LOG = 19, inf = 1e18;
vector<vector<int>> adj, up;
vector<pair<int, int>> edges, queries, check, coin;
vector<int> in_time, out_time;
int timer = 0;

struct Fenwick{
    int n; vector<int> tree;
    Fenwick(int _n) : n(_n + 5), tree(_n + 5, 0) {}
    void _update(int pos, int val){
        for(pos++; pos < n; pos += pos & (-pos)) tree[pos] += val;
    } int query(int pos){
        int res = 0;
        for(pos++; pos > 0; pos -= pos & (-pos)) res += tree[pos];
        return res;
    } void update(int in, int out, int val){
        _update(in, val), _update(out + 1, -val);
    }
};

void dfs(int u, int par){
    in_time[u] = ++timer;
    up[u][0] = par;
    for(int i = 1; i < LOG; i++)
        if(up[u][i - 1] != -1) up[u][i] = up[up[u][i - 1]][i - 1];
    for(const int &v : adj[u])
        if(v != par) dfs(v, u);
    out_time[u] = timer;
}

bool is_ances(int u, int v){
    return in_time[u] <= in_time[v] && out_time[v] <= out_time[u];
}

int _lca(int u, int v){
    if(is_ances(u, v)) return u;
    if(is_ances(v, u)) return v;
    for(int i = LOG - 1; i >= 0; i--)
        if(up[u][i] != -1 &&!is_ances(up[u][i], v)) u = up[u][i];
    return up[u][0];
}

void solve(){
    int n, m, q; cin >> n >> m >> q;
    adj.resize(n + 1), up.resize(n + 1, vector<int> (LOG, -1));
    in_time.resize(n + 1), out_time.resize(n + 1);
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        edges.push_back({u, v});
        adj[u].push_back(v), adj[v].push_back(u);
    } for(int i = 0; i < m; i++){
        int p, c; cin >> p >> c;
        check.push_back({p, c}); 
    } sort(check.begin(), check.end(), [&](pair<int, int> a, pair<int, int> b){
        if(a.second == b.second) return a.first < b.first;
        return a.second < b.second;
    });
    dfs(1, -1);
    for(int i = 1; i < n; i++){
        if(is_ances(edges[i - 1].second, edges[i - 1].first)) swap(edges[i - 1].first, edges[i - 1].second);
    } vector<pair<int, int>> queries(q);
    vector<int> lca(q);
    for(int i = 0; i < q; i++){
        int g, s;
        cin >> queries[i].first >> queries[i].second >> g >> s;
        coin.push_back({g, s});
        lca[i] = _lca(queries[i].first, queries[i].second);
    } vector<int> le(q, 0), ri(q, m), res(q, inf);
    bool cont = true;
    int turn = 0;
    while(cont){
        turn++;
        cont = false;
        vector<vector<int>> bucket(m + 1);
        for(int i = 0; i < q; i++){
            if(le[i] != ri[i]){
                cont = true;
                int mid = (le[i] + ri[i] + 1) / 2;
                bucket[mid].push_back(i); 
            } 
        } Fenwick bit_sil(timer), bit_gol(timer);
        for(int i = 0; i <= m; i++){
            if(i != 0){
                const auto &[p, c] = check[i - 1];
                bit_sil.update(in_time[edges[p - 1].second], out_time[edges[p - 1].second], c);
                bit_gol.update(in_time[edges[p - 1].second], out_time[edges[p - 1].second], 1); 
            } for(const int &q : bucket[i]){
                const auto &[u, v] = queries[q];
                int l = lca[q];
                int sil = bit_sil.query(in_time[u]) + bit_sil.query(in_time[v]) - 2 * bit_sil.query(in_time[l]);
                int gol = bit_gol.query(in_time[u]) + bit_gol.query(in_time[v]) - 2 * bit_gol.query(in_time[l]);
                if(sil <= coin[q].second) le[q] = i, res[q] = gol;
                else ri[q] = i - 1;
            }
        } 
    } Fenwick bit(timer);
    for(int i = 0; i < m; i++){
        const auto &[p, c] = check[i];
        int idx = edges[p - 1].second;
        bit.update(in_time[idx], out_time[idx], 1);
    }  for(int i = 0; i < q; i++){
        const auto &[u, v] = queries[i];
        if(res[i] == inf) res[i] = 0;
        cout << max((long long)-1, coin[i].first - (bit.query(in_time[u]) + bit.query(in_time[v]) - 2 * bit.query(in_time[lca[i]]) - res[i])) << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test;
    test = 1;
    //cin >> test;
    while(test--) solve();
}

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