제출 #1308108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308108		sweetwibu2k8	Two Currencies (JOI23_currencies)	C++20	0 / 100	2 ms	976 KiB

currencies

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

#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int,int> pii;

const int M = 1e5 + 6;

int n, m, q;
vector<int> g[M];
pii e[M];
int cost[M], in[M], out[M];
int anc[M][18], depth[M];
int d[M], ini[M], Lca[M];
int timedfs = 0;
ll L[M], R[M], MID[M], ans[M];

struct query {
    int s, t;
    ll x, y;
} Q[M];

struct Fenwick {
    ll f[M];
    int n;
    void resize(int x) { n = x; fill(f, f + n + 1, 0); }
    void update(int i, int val) { 
        for (; i <= n; i += i & -i) f[i] += val; 
    }
    ll GET(int i) {
        ll res = 0;
        for (; i > 0; i -= i & -i) res += f[i];
        return res;
    }
} BIT, CNT;

void dfs(int u, int p) {
    in[u] = ++timedfs;
    anc[u][0] = p;
    for (int v : g[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
    out[u] = timedfs;
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = 17; k >= 0; k--)
        if (depth[u] - (1 << k) >= depth[v]) u = anc[u][k];
    if (u == v) return u;
    for (int k = 17; k >= 0; k--)
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    return anc[u][0];
}

void prework(int u, int p) {
    for (int v : g[u]) {
        if (v == p) continue;
        d[v] += d[u];
        prework(v, u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n >> m >> q)) return 0;

    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
        e[i] = {u, v};
    }

    memset(cost, -1, sizeof(cost));
    for (int i = 1; i <= m; i++) {
        int p, c; cin >> p >> c;
        cost[p] = c;
    }

    dfs(1, 0);
    for (int k = 1; k < 18; k++)
        for (int i = 1; i <= n; i++)
            anc[i][k] = anc[anc[i][k-1]][k-1];

    // Đảm bảo e[i].se luôn là nút con
    for (int i = 1; i < n; i++)
        if (depth[e[i].fi] > depth[e[i].se]) swap(e[i].fi, e[i].se);

    vector<int> id;
    for (int i = 1; i < n; i++) {
        if (cost[i] != -1) {
            id.pb(i);
            d[e[i].se] = 1; // Đánh dấu cạnh có thể sử dụng
        }
    }
    sort(all(id), [](int a, int b) { return cost[a] < cost[b]; });
    
    prework(1, 0);

    for (int i = 1; i <= q; i++) {
        cin >> Q[i].s >> Q[i].t >> Q[i].x >> Q[i].y;
        Lca[i] = get_lca(Q[i].s, Q[i].t);
        ini[i] = d[Q[i].s] + d[Q[i].t] - 2 * d[Lca[i]];
        L[i] = 0; R[i] = 1e9;
        ans[i] = Q[i].x - ini[i]; // Mặc định là x trừ đi tổng số cạnh có giá (chưa khôi phục cái nào)
    }

    while (true) {
        vector<int> queries;
        for (int i = 1; i <= q; i++) if (L[i] <= R[i]) queries.pb(i);
        if (queries.empty()) break;

        sort(all(queries), [](int a, int b) { return (L[a] + R[a]) / 2 < (L[b] + R[b]) / 2; });

        BIT.resize(n);
        CNT.resize(n);
        int pt = 0;
        for (int i : queries) {
            ll mid = (L[i] + R[i]) / 2;
            while (pt < id.size() && cost[id[pt]] <= mid) {
                int v = e[id[pt]].se;
                BIT.update(in[v], cost[id[pt]]);
                BIT.update(out[v] + 1, -cost[id[pt]]);
                CNT.update(in[v], 1);
                CNT.update(out[v] + 1, -1);
                pt++;
            }

            ll current_cost = BIT.GET(in[Q[i].s]) + BIT.GET(in[Q[i].t]) - 2 * BIT.GET(in[Lca[i]]);
            ll count_edges = CNT.GET(in[Q[i].s]) + CNT.GET(in[Q[i].t]) - 2 * CNT.GET(in[Lca[i]]);

            if (current_cost <= Q[i].y) {
                ans[i] = Q[i].x - ini[i] + count_edges;
                L[i] = mid + 1;
            } else {
                R[i] = mid - 1;
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << (ans[i] < 0 ? -1 : ans[i]) << endl;
    }

    return 0;
}

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