Submission #1308088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308088		duongquanghai08	Two Currencies (JOI23_currencies)	C++20	100 / 100	921 ms	40652 KiB

currencies

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 5;
int n, m, q;
vector<int> adj[N];
int par[N][20], in[N], out[N], depth[N];
pii E[N], Q[N];
int cnt = 0;
int S[N], T[N], X[N], Lca[N];
long long Y[N];
int L[N], R[N];
vector<int> id[N];
int ans[N];
struct BIT{
    long long tree[N];
    void reset() {
        memset(tree, 0, sizeof(tree));
    }
    void update(int i, int val) {
        for(; i <= n; i += i & -i) tree[i] += val;
    }
    long long get(int i) {
        long long res = 0;
        for(; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
};
BIT BIT1, BIT2;
void dfs(int u) {
    in[u] = ++cnt;
    for(auto v : adj[u]) {
        if(v == par[u][0]) continue;
        par[v][0] = u;
        depth[v] = depth[u] + 1;
        for(int i = 1; i <= 18; i++) par[v][i] = par[par[v][i - 1]][i - 1];
        dfs(v);
    }
    out[u] = cnt;
}
int lca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    int len = depth[u] - depth[v];
    for(int i = 18; i >= 0; i--) if((len >> 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];
}
void Solve() {
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        E[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    for(int i = 1; i < n; i++) if(lca(E[i].fi, E[i].se) == E[i].se) swap(E[i].fi, E[i].se);
    for(int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        Q[i] = {y, x};
    }
    sort(Q + 1, Q + m + 1);
    for(int i = 1; i <= q; i++) {
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        Lca[i] = lca(S[i], T[i]);
        L[i] = 0;
        R[i] = m;
    }
    while(true) {
        bool ok = true;
        for(int i = 1; i <= m; i++) id[i].clear();
        for(int i = 1; i <= q; i++) {
          //  cout << i << " " << L[i] << " " << R[i] << '\n';
            if(L[i] <= R[i]) {
                int mid = (L[i] + R[i]) / 2;
                id[mid].push_back(i);
                ok = false;
            }
        }
        if(ok) break;
        BIT1.reset();
        BIT2.reset();
        for(int i = 1; i <= m; i++) {
            int u = E[Q[i].se].se;
            BIT1.update(in[u], 1);
            BIT1.update(out[u] + 1, -1);
        }
        for(int i = 0; i <= m + 1; i++) {
            int u = E[Q[i].se].se;
            if(i >= 1 && i <= m) {
                BIT1.update(in[u], -1);
                BIT1.update(out[u] + 1, 1);
                BIT2.update(in[u], Q[i].fi);
                BIT2.update(out[u] + 1, -Q[i].fi);
            }
            for(auto x : id[i]) {
                long long sum = BIT2.get(in[S[x]]) + BIT2.get(in[T[x]]) - 2 * BIT2.get(in[Lca[x]]);
                if(sum <= Y[x]) {
                    ans[x] = BIT1.get(in[S[x]]) + BIT1.get(in[T[x]]) - 2 * BIT1.get(in[Lca[x]]);
                    L[x] = i + 1;
                }
                else R[x] = i - 1;

            }
        }
    }
    for(int i = 1; i <= q; i++) {
        cout << max(-1, X[i] - ans[i]) << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
}

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