Submission #1296584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296584		tranthienphuc2657	Two Currencies (JOI23_currencies)	C++20	100 / 100	520 ms	47968 KiB

currencies

// Thuy Ttienn
// 14 ngày trước khi tới sinh nhật Tiên 24/7.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Sz(x) ((int) (x).size())
#define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {if (a > b) a = b; else return 0; return 1;}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {if (a < b) a = b; else return 0; return 1;}
const int inf = 2e9 + 7;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, m, q;
vector <int> a[N];
pair <int, int> edge[N];
vector <pair <int, int>> c; 
int s[N], t[N], gold[N];
ll silver[N];
int l[N], r[N], num[N];

int st[2 * N], tour[2 * N], h[N], tourDfs = 0;
int LCA[20][2 * N];

int stId[N], edId[N], idDfs = 0;

vector <int> query[N];
int res[N];

void dfs(int u, int pre) {
    tour[++tourDfs] = u;
    st[u] = tourDfs;
    stId[u] = ++idDfs;
    for (int v: a[u]) if (v != pre) {
        h[v] = h[u] + 1;
        dfs(v, u);
        tour[++tourDfs] = u;
    }
    edId[u] = idDfs;
}

#define Min(a, b) ((h[a] < h[b]) ? a : b)
void prepare_lca() {
    for (int i = 1; i <= tourDfs; i++) LCA[0][i] = tour[i];
    for (int lg = 1; (1 << lg) <= tourDfs; lg++) 
        for (int i = 1; i + (1 << lg) - 1 <= tourDfs; i++) 
            LCA[lg][i] = Min(LCA[lg - 1][i], LCA[lg - 1][i + (1 << (lg - 1))]);
}

int lca(int u, int v) {
    if (st[u] > st[v]) swap(u, v);
    int lg = 31 - __builtin_clz(st[v] - st[u] + 1);
    return Min(LCA[lg][st[u]], LCA[lg][st[v] - (1 << lg) + 1]);
}

struct Fenwick_tree {
    ll BIT[N];

    void reset() {
        memset(BIT, 0, sizeof(BIT));
    }

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

    void update_node(int u, ll val) {
        update(stId[u], val);
        update(edId[u] + 1, -val);
    }

    ll get(int k) {
        ll res = 0;
        for (; k >= 1; k -= k & (-k)) res += BIT[k];
        return res;
    }

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

    ll get_path(int u, int v) {
        int Lca = lca(u, v);
        return get(stId[Lca] + 1, stId[u]) + get(stId[Lca] + 1, stId[v]);
    }
} allStation, numStation, valStation;

bool check(int id) {
    return valStation.get_path(s[id], t[id]) <= silver[id];
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    file("");

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
        edge[i] = {u, v};
    }
    dfs(1, 1);
    prepare_lca();
    c.push_back({-1, -1});
    for (int i = 1; i <= m; i++) {
        int pos, coin; cin >> pos >> coin;
        pair <int, int> e = edge[pos];
        int u = e.first, v = e.second;
        if (stId[u] > stId[v]) swap(u, v);
        c.push_back({coin, v});
    }
    sort(c.begin(), c.end());

    for (int i = 1; i <= q; i++) cin >> s[i] >> t[i] >> gold[i] >> silver[i];
    for (int i = 1; i <= q; i++) {
        l[i] = 0;
        r[i] = m;
    }
    
    while (true) {
        for (int i = 0; i <= m; i++) query[i].clear();
        numStation.reset();
        valStation.reset();

        bool checker = false;
        for (int i = 1; i <= q; i++) if (l[i] <= r[i]) {
            query[(l[i] + r[i]) / 2].push_back(i);
            checker = true;
        }
        if (!checker) break;

        for (int i = 0; i <= m; i++) {
            if (i) {
                int u = c[i].second, val = c[i].first;
                numStation.update_node(u, 1);
                valStation.update_node(u, val);
            }

            for (int x: query[i]) 
                if (check(x)) {
                    l[x] = i + 1;
                    num[x] = numStation.get_path(s[x], t[x]);
                }
                else r[x] = i - 1;
        }
    }

    for (int i = 1; i <= m; i++) allStation.update_node(c[i].second, 1);

    for (int i = 1; i <= q; i++) {
        int x = allStation.get_path(s[i], t[i]) - num[i];
        res[i] = ((gold[i] >= x) ? gold[i] - x : -1);
    }

    for (int i = 1; i <= q; i++) cout << res[i] << "\n";
    cerr << "Time elapsed: " << TIME << "s.\n";
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:7:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:96:5: note: in expansion of macro 'file'
   96 |     file("");
      |     ^~~~
currencies.cpp:7:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:96:5: note: in expansion of macro 'file'
   96 |     file("");
      |     ^~~~

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