Submission #958940

#	Time	Username	Problem	Language	Result	Execution time	Memory
958940		Valaki2	Two Currencies (JOI23_currencies)	C++14	100 / 100	1532 ms	59272 KiB

currencies

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1e5 + 1;

int n, m, q;
vector<pii > ori_graph[1 + maxn];
int conv[1 + maxn];
vector<pii > graph[1 + maxn];
int road[1 + maxn];
int cost[1 + maxn];
vector<int> by_road[1 + maxn];
int node_cnt;
int from[1 + maxn];
int to[1 + maxn];
int gold[1 + maxn];
int silver[1 + maxn];

void virtual_dfs(int cur, int par) {
    for(pii nei : ori_graph[cur]) {
        if(nei.fi == par) {
            continue;
        }
        if(by_road[nei.se].empty()) {
            conv[nei.fi] = conv[cur];
            virtual_dfs(nei.fi, cur);
        } else {
            int last = conv[cur];
            for(int check_id : by_road[nei.se]) {
                node_cnt++;
                int nxt = node_cnt;
                graph[last].pb(mp(nxt, check_id));
                graph[nxt].pb(mp(last, check_id));
                last = nxt;
            }
            conv[nei.fi] = last;
            virtual_dfs(nei.fi, cur);
        }
    }
}

int visit_time;
int in[1 + maxn];
int out[1 + maxn];
int par_edge[1 + maxn];
int which[1 + 2 * maxn];

void dfs_euler(int cur, int par) {
    visit_time++;
    in[cur] = visit_time;
    for(pii nei : graph[cur]) {
        if(nei.fi == par) {
            par_edge[cur] = nei.se;
        } else {
            dfs_euler(nei.fi, cur);
        }
    }
    visit_time++;
    out[cur] = visit_time;
}

const int block_size = 320;
const int blocks = 320;

int block(int pos) {
    return (pos - 1) / block_size + 1;
}

struct query {
    int l, r, idx;
    bool except;
    bool operator < (const query &other) const {
        if(block(l) != block(other.l)) {
            return block(l) < block(other.l);
        }
        return r < other.r;
    }
};

int ans[1 + maxn];
bool counted_in[1 + maxn];
int block_sum[1 + maxn];
int single_sum[1 + 2 * maxn];
int block_cnt[1 + maxn];
int single_cnt[1 + 2 * maxn];
int ord[1 + maxn];
int ord_cost[1 + maxn];
int total_cnt;

void add(int cur) {
    cur = par_edge[cur];
    cur = ord[cur];
    block_sum[block(cur)] += ord_cost[cur];
    single_sum[cur] += ord_cost[cur];
    block_cnt[block(cur)]++;
    single_cnt[cur]++;
    total_cnt++;
}

void rem(int cur) {
    cur = par_edge[cur];
    cur = ord[cur];
    block_sum[block(cur)] -= ord_cost[cur];
    single_sum[cur] -= ord_cost[cur];
    block_cnt[block(cur)]--;
    single_cnt[cur]--;
    total_cnt--;
}

void toggle(int cur) {
    cur = which[cur];
    if(cur == 1) {
        return;
    }
    if(!counted_in[cur]) {
        add(cur);
        counted_in[cur] = true;
    } else {
        rem(cur);
        counted_in[cur] = false;
    }
}

void solve_queries() {
    vector<query> queries;
    for(int i = 1; i <= q; i++) {
        int a = from[i], b = to[i];
        if(in[a] > in[b]) {
            swap(a, b);
        }
        if(in[a] <= in[b] && out[b] <= out[a]) {
            queries.pb(query {in[a], in[b], i, true});
        } else {
            queries.pb(query {out[a], in[b], i, false});
        }
    }
    sort(queries.begin(), queries.end());
    int l = 1, r = 0;
    for(query cur : queries) {
        if(from[cur.idx] == to[cur.idx]) {
            ans[cur.idx] = gold[cur.idx];
            continue;
        }
        while(l > cur.l) {
            l--;
            toggle(l);
        }
        while(r < cur.r) {
            r++;
            toggle(r);
        }
        while(l < cur.l) {
            toggle(l);
            l++;
        }
        while(r > cur.r) {
            toggle(r);
            r--;
        }
        if(cur.except) {
            toggle(l);
        }
        int limit = silver[cur.idx];
        /*if(cur.idx == 1) {
            cout << from[cur.idx] << " " << to[cur.idx] << "\n";
            cout << total_cnt << "\n";
            for(int i = 1; i <= m; i++) {
                cout << counted_in[i];
            }
            cout << "\n";
        }*/
        int cur_sum = 0, cur_cnt = 0;
        int res = 0;
        for(int i = 1; i <= blocks; i++) {
            if(cur_sum + block_sum[i] <= limit) {
                cur_sum += block_sum[i];
                cur_cnt += block_cnt[i];
            } else {
                for(int j = block_size * (i - 1) + 1; j <= block_size * i; j++) {
                    if(cur_sum <= limit) {
                        // if(cur.idx == 1) cout << "! " << res << " " << cur_cnt << "\n";
                        res = max(res, cur_cnt);
                    } else {
                        break;
                    }
                    if(cur.idx == 1) {
                        // cout << j << " - " << single_sum[j] << " - " << single_cnt[j] << "\n";
                        // pedig kellene kiirnia valamit
                    }
                    cur_sum += single_sum[j];
                    cur_cnt += single_cnt[j];
                }
            }
        }
        if(cur_sum <= limit) {
            // if(cur.idx == 1) cout << "! " << res << " " << cur_cnt << "\n";
            res = max(res, cur_cnt);
        }
        res = total_cnt - res;
        res = gold[cur.idx] - res;
        if(res < 0) {
            res = -1;
        }
        ans[cur.idx] = res;
        if(cur.except) {
            toggle(l);
        }
    }
}

void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        ori_graph[a].pb(mp(b, i));
        ori_graph[b].pb(mp(a, i));
    }
    for(int i = 1; i <= m; i++) {
        cin >> road[i] >> cost[i];
        by_road[road[i]].pb(i);
    }
    for(int i = 1; i <= q; i++) {
        cin >> from[i] >> to[i] >> gold[i] >> silver[i];
    }
    conv[1] = 1;
    node_cnt = 1;
    virtual_dfs(1, -1);
    /*for(int i = 1; i <= n; i++) {
        cout << conv[i] << " ";
    }
    cout << "\n" << node_cnt << "\n";
    for(int i = 1; i <= m + 1; i++) {
        cout << i << ":\n";
        for(pii j : graph[i]) {
            cout << j.fi << " " << j.se << "; ";
        }
        cout << "\n";
    }*/
    n = m + 1;
    for(int i = 1; i <= q; i++) {
        from[i] = conv[from[i]];
        to[i] = conv[to[i]];
    }
    dfs_euler(1, -1);
    for(int i = 1; i <= n; i++) {
        which[in[i]] = which[out[i]] = i;
    }
    vector<pii > cost_order;
    for(int i = 1; i <= m; i++) {
        cost_order.pb(mp(cost[i], i));
    }
    sort(cost_order.begin(), cost_order.end());
    for(int i = 0; i < m; i++) {
        ord[cost_order[i].se] = i + 1;
        ord_cost[i + 1] = cost_order[i].fi;
    }
    /*for(int i = 1; i <= m; i++) {
        cout << ord[i] << " " << ord_cost[i] << "\n";
    }
    cout << "\n";*/
    solve_queries();
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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