Submission #1308121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308121		viobow	Two Currencies (JOI23_currencies)	C++17	100 / 100	2097 ms	70072 KiB

currencies

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define re exit(0);
#define FOR(i, a, b)   for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b)  for(int i = (a), _b = (b); i >= _b; i--)
#define LOOP(a)        for(int i = 0, _a = (a); i < _a; i++)
#define left id<<1
#define right id<<1|1
#define _lower(v, x) lower_bound(v.begin(), v.end(), x) - v.begin() + 1
#define ever ;;
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

template<typename T> void chkmin(T &x, T y) {if (y < x) x = y;}
template<typename T> void chkmax(T &x, T y) {if (y > x) x = y;}

const int mod = 1e9 + 7;
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int _pow(int a, int b) {
   int ans = 1;
   while (b) {
   if (b % 2 == 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b /= 2;
   }
   return ans;
}

//--------------------------------------------------------------------------------------------------------------------------------------

const int maxn = 2e5;

struct Edge {
    int u, v, check_point_count;
};
struct CheckPoint {
    int u, v, w;
    bool operator< (const CheckPoint &other) const {
        return w < other.w;
    }
};
struct Que {
    int s, t, gold, silver;
};
struct Fenwick_Tree {
    int BIT[maxn + 5]; int n;
    void init(int _n) {
        n = _n;
        FOR(i, 0, n + 2) BIT[i] = 0;
    }
    void update(int pos, int val) {
        while (pos <= n) {
            BIT[pos] += val;
            pos += pos & -pos;
        }
    }
    void update(int l, int r, int val) {
        update(l, val);
        update(r + 1, -val);
    }
    int get(int pos) {
        int res = 0;
        while (pos) {
            res += BIT[pos];
            pos -= pos & -pos;
        }
        return res;
    }
};

vii adjList[maxn + 5];
bool costed[maxn + 5];
Edge e[maxn + 5]; CheckPoint cp[maxn + 5]; Que query[maxn + 5];
int n, numCheckPoint, numQuery;

vector<int> bucket[maxn + 5];
int l[maxn + 5], r[maxn + 5], silver_road[maxn + 5];
Fenwick_Tree sum_cost, sum_used;
int timeDfs, tin[maxn + 5], tout[maxn + 5], dep[maxn + 5], check_point_dep[maxn + 5], par[maxn + 5][20];

void pre_dfs(int u, int p) {
    tin[u] = ++timeDfs;
    for (auto [v, check_point_count] : adjList[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        check_point_dep[v] = check_point_dep[u] + check_point_count;
        par[v][0] = u;
        for (int i = 1; i <= 18; i++)
            par[v][i] = par[par[v][i - 1]][i - 1];
        pre_dfs(v, u);
    }
    tout[u] = timeDfs;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int h = dep[u] - dep[v];
    for (int i = 0; i <= 18; i++) if (h >> i & 1) u = par[u][i];
    if (u == v) return u;
    for (int i = 18; i >= 0; i--) if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

int check_point_count_on_path(int u, int v) {
    return check_point_dep[u] + check_point_dep[v] - 2 * check_point_dep[lca(u, v)];
}

int used_on_path(int u, int v) {
    return sum_used.get(tin[u]) + sum_used.get(tin[v]) - 2 * sum_used.get(tin[lca(u, v)]);
}
int cost_on_path(int u, int v) {
    return sum_cost.get(tin[u]) + sum_cost.get(tin[v]) - 2 * sum_cost.get(tin[lca(u, v)]);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //#define name "mooo"
    //if (fopen(name".inp", "r")) {
    //    freopen(name".inp", "r", stdin);
    //    freopen(name".out", "w", stdout);
    //}

    cin >> n >> numCheckPoint >> numQuery;
    FOR(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        e[i] = {u, v, 0};
    }

    FOR(i, 1, numCheckPoint) {
        int idx, w; cin >> idx >> w;
        int u = e[idx].u, v = e[idx].v;
        e[idx].check_point_count += 1;
        cp[i] = {u, v, w};
    }

    FOR(i, 1, n - 1) {
        auto [u, v, check_point_count] = e[i];
        adjList[u].pb({v, check_point_count});
        adjList[v].pb({u, check_point_count});
    }

    pre_dfs(1, 0);

    FOR(i, 1, numCheckPoint) {
        auto& [u, v, w] = cp[i];
        if (par[v][0] != u) swap(u, v);
    }

    sort(cp + 1, cp + numCheckPoint + 1);

    FOR(i, 1, numQuery) {
        int s, t, gold, silver;
        cin >> s >> t >> gold >> silver;
        query[i] = {s, t, gold, silver};
    }

    FOR(i, 1, numQuery)
        l[i] = 1, r[i] = numCheckPoint;

    bool process = 0;
    for(ever) {
        process = 0;
        FOR(i, 1, numQuery)
            if (l[i] <= r[i])
                process = 1;
        if (!process) break;

        //reset stuff
        FOR(i, 1, numCheckPoint)
            bucket[i].clear();
        sum_cost.init(n); sum_used.init(n);
        //

        FOR(i, 1, numQuery)
            if (l[i] <= r[i])
                bucket[(l[i] + r[i]) >> 1].pb(i);

        for (int bound = 1; bound <= numCheckPoint; bound++) {
            int v = cp[bound].v, w = cp[bound].w;
            sum_cost.update(tin[v], tout[v], +w);
            sum_used.update(tin[v], tout[v], +1);

            for (int queryID : bucket[bound]) {
                auto [s, t, gold, silver] = query[queryID];
                if (cost_on_path(s, t) <= silver)
                    silver_road[queryID] = used_on_path(s, t), l[queryID] = bound + 1;
                else
                    r[queryID] = bound - 1;
            }
        }
    }

    FOR(queryID, 1, numQuery) {
        auto [s, t, gold, silver] = query[queryID];
        int gold_road = check_point_count_on_path(s, t) - silver_road[queryID];
        int res = gold - gold_road;
        if (res < 0) res = -1;
        cout << res << '\n';
    }

    return 0;
}

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