Submission #1247311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247311		hypersphere	Two Currencies (JOI23_currencies)	C++17	100 / 100	891 ms	30652 KiB

currencies

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

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

const ll mod = 1e9 + 7;
const ll mod2 = 1e9 + 6;
const ll INF = 2e18;
const int INT_INF = 1e9 + 11;
 
long long binpow(long long base, long long power, long long mod) {
    if (base == 0) return 0;
    if (base == 1) return 1;
    if (power <= 0) return 1;
    long long multiplier = (power % 2 == 0 ? 1 : base) % mod;
    return (multiplier * binpow((base * base) % mod, power / 2, mod)) % mod;
}

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

const int N = 1e5 + 5;
const int LOGN = 18;

vector<int> adj[N];
pair<int, int> edges[N];
pair<int, int> checkpoints[N]; // First is cost and second is index
int binlift[N][LOGN];
int in[N], out[N];

int timer = 0;

void fill_binlift(int node, int prev){
    binlift[node][0] = prev;
    for(int lift = 1; lift < LOGN; lift++){
        int half_way = binlift[node][lift - 1];
        if(half_way == -1) break;

        binlift[node][lift] = binlift[half_way][lift - 1];
    }
}
void euler_tour(int node, int prev = -1){
    in[node] = ++timer;

    fill_binlift(node, prev);
    for(int v : adj[node]){
        if(v == prev) continue;
        euler_tour(v, node);
    }

    out[node] = timer;
}

bool is_ancestor(int parent, int child){
    assert(parent != -1 && child != -1);

    return (in[parent] <= in[child] && out[parent] >= out[child]);
}

int lca(int a, int b){
    assert(a != -1 && b != -1);

    if(in[a] > in[b]) swap(a, b);
    if(is_ancestor(a, b)) return a;
    if(is_ancestor(b, a)) return b;

    int cur = b;
    for(int lift = LOGN - 1; lift >= 0; lift--){
        int lifted = binlift[cur][lift];

        if(lifted == -1) continue;
        if(is_ancestor(lifted, a)) continue;

        cur = lifted;
    }
    // Cur is one away
    return binlift[cur][0];
}

void reorder_edges(){
    for(int i = 1; i < N; i++){
        if(edges[i].first == 0) break;
        if(is_ancestor(edges[i].second, edges[i].first)) swap(edges[i].first, edges[i].second);
    }
}

struct Fenwick{
    int n;
    vector<ll> tree;
    Fenwick(int n = 0) : n(n), tree(n, 0){

    }

    void update(int pos, ll val){
        for(int i = pos; i < n; i += (i & -i)) tree[i] += val;
    }

    ll get(int pos){
        ll ans = 0;
        for(int i = pos; i > 0; i -= (i & -i)) ans += tree[i];
        return ans;
    }
};

struct Query{
    int start, end;
    ll gold, silver;

    Query(int start = 0, int end = 0, ll gold = 0, ll silver = 0) : start(start), end(end), gold(gold), silver(silver){

    }
};

void Run(){
    for(int i = 0; i < N; i++) for(int j = 0; j < LOGN; j++) binlift[i][j] = -1;

    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);

        edges[i] = {a, b};
    }
    euler_tour(1);
    reorder_edges(); // To ensure that the ancestor is always the first element

    Fenwick checkpoint_tree(n + 3); // Holds number of checkpoints from root to this node
    for(int i = 1; i <= m; i++){
        int p; ll c; 
        cin >> p >> c;

        int l = in[edges[p].second];
        int r = out[edges[p].second];
        checkpoint_tree.update(l, 1);
        checkpoint_tree.update(r + 1, -1);

        checkpoints[i] = {c, p};
    }
    sort(checkpoints + 1, checkpoints + m + 1);

    vector<Query> queries(q);
    for(int i = 0; i < q; i++){
        ll s, t, gold, sil;
        cin >> s >> t >> gold >> sil;
        queries[i] = Query(s, t, gold, sil);
    }

    vector<int> left(q, 0);
    vector<int> right(q, m);
    vector<int> ans(q, 0);
    
    int times = LOGN + 1;
    while(times--){
        // Clearing
        Fenwick silver_tree(n + 3); // Holds sum of silver used
        vector<vector<int>> candidates(m + 1); // Hold candidates for each mid

        // Update mid for every intervals
        for(int i = 0; i < q; i++){
            if(left[i] < right[i]){
                int mid = (left[i] + right[i] + 1) / 2;
                candidates[mid].push_back(i);
            } else{
                ans[i] = left[i];
            }
        }

        // Events: update the edges
        for(int mid = 0; mid <= m; mid++){
            // Update
            if(mid != 0){
                pair<int, int> edge = edges[checkpoints[mid].second];
                int l = in[edge.second];
                int r = out[edge.second];

                silver_tree.update(l, checkpoints[mid].first);
                silver_tree.update(r + 1, -checkpoints[mid].first);
            }

            // Answer queries
            for(int cand : candidates[mid]){
                ll silver_used = 
                    silver_tree.get(in[queries[cand].start])
                    + silver_tree.get(in[queries[cand].end])
                    - 2 * silver_tree.get(in[lca(queries[cand].start, queries[cand].end)]);

                if(silver_used > queries[cand].silver){
                    right[cand] = mid - 1;
                } else left[cand] = mid;
            }
        }
    }

    vector<vector<int>> candidates(m + 1);
    vector<ll> ans_queries(q);
    for(int i = 0; i < q; i++) candidates[ans[i]].push_back(i);

    // Answer each query
    Fenwick active_tree(n + 3);
    for(int mid = 0; mid <= m; mid++){
        // Update
        if(mid != 0){
            pair<int, int> edge = edges[checkpoints[mid].second];
            int l = in[edge.second];
            int r = out[edge.second];

            active_tree.update(l, 1);
            active_tree.update(r + 1, -1);
        }

        // Answer queries
        for(int cand : candidates[mid]){
            ll gold_saved = 
                active_tree.get(in[queries[cand].start])
                + active_tree.get(in[queries[cand].end])
                - 2 * active_tree.get(in[lca(queries[cand].start, queries[cand].end)]);

            ll checkpoints_on_the_way = 
                checkpoint_tree.get(in[queries[cand].start])
                + checkpoint_tree.get(in[queries[cand].end])
                - 2 * checkpoint_tree.get(in[lca(queries[cand].start, queries[cand].end)]);

            ll remaining_gold = queries[cand].gold + gold_saved - checkpoints_on_the_way;

            if(remaining_gold < 0){
                ans_queries[cand] = -1;
            } else{
                ans_queries[cand] = remaining_gold;
            }
        }
    }

    for(int i = 0; i < q; i++) cout << ans_queries[i] << "\n";
}

int main(){
    //freopen("CIRSSTR.INP", "r", stdin);
    //freopen("CIRSSTR.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
 
    int test = 1;
    //cin >> test;

    // Measuring running time (breaks when manual input)
    //auto time_start = clock();
    while(test--) Run();
    //auto time_end = clock();

    //cerr << "Time taken: " << time_end - time_start << "\n";
}

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