Submission #1248699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248699		MinhKien	Two Currencies (JOI23_currencies)	C++20	100 / 100	1112 ms	40616 KiB

currencies

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define ll long long
const int N = 2e5 + 10;

int n, m, k;
int sz[N], par[N], depth[N];
int ChainID[N], ChainHead[N], pos[N], CurChain = 1, CurPos;
int L[N], R[N], bin[N];
vector <int> g[N];
vector <int> queries[N];

struct edge {
    int u, v;

    void inp(int i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(i);
        g[v].push_back(i);
    }
} e[N];

struct CheckPoint {
    int id;
    ll silver;

    bool operator < (const CheckPoint &o) const {
        return silver < o.silver;
    }

    void inp() {
        scanf("%d%lld", &id, &silver);
    }
} p[N];

struct Query {
    int s, t, gold, id, ans;
    ll silver;

    void inp(int i) {
        scanf("%d%d%d%lld", &s, &t, &gold, &silver);
        id = i;
    }

    bool operator < (const Query &o) const {
        return id < o.id;
    }
} q[N];

bool cmp_query(const Query &A, const Query &B) {
    return bin[A.id] > bin[B.id];
}

struct BIT {
    ll val[N];

    void clear() {
        fill_n(val, n + 1, 0);
    }

    void update(int p, ll VAL) {
        while (p <= n) {
            val[p] += VAL;
            p += p & -p;
        }
    }

    ll get(int p) {
        ll ret = 0;
        while (p > 0) {
            ret += val[p];
            p -= p & -p;
        }
        return ret;
    }

    ll range(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
} bit;

void input() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i < n; ++i) e[i].inp(i);
    for (int i = 1; i <= m; ++i) p[i].inp();
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= k; ++i) {
        L[i] = 0;
        R[i] = m;
        q[i].inp(i);
    }
}

int DFS(int s = 1, int p = -1) {
    sz[s] = 1;
    for (int id: g[s]) {
        int z = e[id].u ^ e[id].v ^ s;
        if (z == p) continue;
        depth[z] = depth[s] + 1;
        par[z] = s;
        sz[s] += DFS(z, s);
    }
    return sz[s];
}

void HLD(int s = 1, int p = -1) {
    if (!ChainHead[CurChain]) {
        ChainHead[CurChain] = s;
    }

    ChainID[s] = CurChain;
    pos[s] = ++CurPos;

    int nxt = 0;
    for (int id: g[s]) {
        int z = e[id].u ^ e[id].v ^ s;
        if (z == p) continue;
        if (sz[nxt] < sz[z]) nxt = z;
    }

    if (!nxt) return;
    HLD(nxt, s);
    for (int id: g[s]) {
        int z = e[id].u ^ e[id].v ^ s;
        if (z == nxt || z == p) continue;
        ++CurChain;
        HLD(z, s);
    }
}

ll GetPath(int u, int v) {
    ll sum = 0;
    while (ChainID[u] != ChainID[v]) {
        if (ChainID[u] < ChainID[v]) swap(u, v);
        sum += bit.range(pos[ChainHead[ChainID[u]]], pos[u]);
        u = par[ChainHead[ChainID[u]]];
    }

    if (depth[u] > depth[v]) swap(u, v);
    sum += bit.range(pos[u] + 1, pos[v]);

    return sum;
}

bool check(int z) {
    return GetPath(q[z].s, q[z].t) <= q[z].silver;
}

void Parallel() {
    for (int i = 1; i < n; ++i) {
        if (pos[e[i].u] < pos[e[i].v]) swap(e[i].u, e[i].v);
    }

    bool ck = true;
    while (true) {
        ck = false;

        for (int i = 1; i <= k; ++i) {
            if (L[i] > R[i]) continue;
            ck = true;
            queries[(L[i] + R[i]) >> 1].push_back(i);
        }

        if (!ck) break;

        for (int z: queries[0]) {
            bin[z] = 0;
            L[z] = 1;
        }

        for (int i = 1; i <= m; ++i) {
            bit.update(pos[e[p[i].id].u], p[i].silver);

            for (int z: queries[i]) {
                if (check(z)) {
                    L[z] = i + 1;
                    bin[z] = i;
                } else R[z] = i - 1;
            }
            queries[i].clear();
        }
        bit.clear();
    }
}

void OutAns() {
    sort(q + 1, q + k + 1, cmp_query);
    int j = m;
    bit.clear();

    for (int i = 1; i <= k; ++i) {
        while (j > bin[q[i].id]) {
            bit.update(pos[e[p[j].id].u], 1);
            --j;
        }

        int need = GetPath(q[i].s, q[i].t);
        if (need <= q[i].gold) {
            q[i].ans = q[i].gold - need;
        } else {
            q[i].ans = -1;
        }
    }

    sort(q + 1, q + k + 1);
    for (int i = 1; i <= k; ++i) {
        cout << q[i].ans << "\n";
    }
}

void solve() {
    input();
    DFS();
    HLD();
    Parallel();
    OutAns();
}

int main() {
    solve();

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void input()':
currencies.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In member function 'void edge::inp(int)':
currencies.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
currencies.cpp: In member function 'void CheckPoint::inp()':
currencies.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d%lld", &id, &silver);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In member function 'void Query::inp(int)':
currencies.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d%d%d%lld", &s, &t, &gold, &silver);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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