Submission #1120742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120742		Yang8on	Two Currencies (JOI23_currencies)	C++17	0 / 100	8 ms	5968 KiB

currencies

#include <bits/stdc++.h>
#define Y8o "TwoCurrencies"
#define maxn (int) 1e5 + 5
#define ll long long
#define pii pair<ll, ll>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b) for(int i = a; i <= b; i ++)
#define fid(i, a, b) for(int i = a; i >= b; i --)
#define int long long

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

int n, m, Q, cnt;
pii ed[maxn];
vector<int> o[maxn];
vector<pii> cur;
int in[maxn], out[maxn], tt[maxn];
int h[maxn], cha[maxn][17];
struct dl { int u, v;; ll golden, silver; } qr[maxn];
int L[maxn], R[maxn];
vector<int> st[maxn];
int ans[maxn];

void dfs(int u = 1, int p = 0) {
    in[u] = ++cnt, tt[u] = cnt;
    for(int v : o[u]) if(v != p) {
        h[v] = h[u] + 1, cha[v][0] = u;
        fi(i, 1, 16) cha[v][i] = cha[ cha[v][i - 1] ][i - 1];
        dfs(v, u);
    }
    out[u] = cnt;
}
int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    int kc = h[u] - h[v];
    fid(i, 16, 0) if(gb(kc, i)) u = cha[u][i];
    fid(i, 16, 0) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
    return u == v ? u : cha[u][0];
}

pii cb(pii x, pii y) {
    return make_pair(x.first + y.first, x.second + y.second);
}
struct BIT {
    pii bit[maxn];

    void build() {
        fi(i, 1, n) bit[i] = { 0, 0 };
    }
    void update(int x, pii val) {
        while(x <= n) {
            bit[x] = cb(bit[x], val);
            x += (x & -x);
        }
    }
    pii get(int x, pii best = {0, 0}) {
        while(x > 0) {
            best = cb(best, bit[x]);
            x -= (x & -x);
        }
        return best;
    }
    void upR(int l, int r, int val) {
        update(l, make_pair(val, +1));
        update(r + 1, make_pair(-val, -1));
    }
} Bit;

void solve() {
    cin >> n >> m >> Q;
    fi(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        o[u].push_back(v), o[v].push_back(u);
        ed[i] = { u, v };
    }
    dfs();
    fi(i, 1, n - 1) {
        int u = ed[i].first, v = ed[i].second;
        if(cha[u][0] == v) swap(ed[i].first, ed[i].second);
    }
    fi(i, 1, m) {
        int id, c; cin >> id >> c;
        cur.push_back({ c, id });
    }

    sort( all(cur) );

    fi(i, 1, Q) {
        int u, v; ll golden, silver;
        cin >> u >> v >> golden >> silver;
        qr[i] = { u, v, golden, silver };
        L[i] = 0, R[i] = (int)cur.size() - 1;
    }

//    fi(id, 1, Q) {
//        int u = qr[id].u, v = qr[id].v, p = lca(u, v);
//        ll golden = qr[id].golden, silver = qr[id].silver;
//
//        int l = 0, r = (int)cur.size() - 1;
//        while(l <= r) {
//            int mid = (l + r) >> 1;
//
//            Bit.build();
//            fi(_, 0, mid) {
//                int val, i; tie(val, i) = cur[_];
//                int u = ed[i].first, v = ed[i].second;
//                Bit.upR(in[v], out[v], val);
//            }
//
//            pii total = cb(Bit.get(in[u]), Bit.get(in[v]));
//            pii del = Bit.get(in[p]); del.first = -2*del.first, del.second = -2*del.second;
//            cb(total, del);
//
//            if(total.first <= silver) l = mid + 1;
//            else r = mid - 1;
//        }
//    }

    while(1) {
        int ok = 1;
        fi(i, 1, Q) if(L[i] <= R[i]) {
            ok = 0;
            st[(L[i] + R[i]) >> 1].push_back(i);
        }

        if(ok) break;
        Bit.build();

        fi(_, 0, (int)cur.size() - 1) {
            int val, i; tie(val, i) = cur[_];
            int u = ed[i].first, v = ed[i].second;
            Bit.upR(in[v], out[v], val);

            while(st[_].size()) {
                int id = st[_].back();
                st[_].pop_back();

                int u = qr[id].u, v = qr[id].v, p = lca(u, v);
                ll golden = qr[id].golden, silver = qr[id].silver;

                pii total = cb(Bit.get(in[u]), Bit.get(in[v]));
                pii del = Bit.get(in[p]); del.first = -2*del.first, del.second = -2*del.second;
                cb(total, del);

                if(silver >= total.first) L[id] = _ + 1;
                else R[id] = _ - 1;
            }
        }
    }

    fi(i, 0, (int)cur.size() - 1) st[i].clear();
    fi(i, 1, Q) {
        int vt = R[i];
        if(vt >= 0) st[vt].push_back(i);
    }

    Bit.build();
    fi(_, 0, (int)cur.size() - 1) {
        int val, i; tie(val, i) = cur[_];
        int u = ed[i].first, v = ed[i].second;
        Bit.upR(in[v], out[v], +val);

        while(st[_].size()) {
            int id = st[_].back(); st[_].pop_back();
            int u = qr[id].u, v = qr[id].v, p = lca(u, v);
            ll golden = qr[id].golden, silver = qr[id].silver;

            pii total = cb(Bit.get(in[u]), Bit.get(in[v]));
            pii del = Bit.get(in[p]); del.first = -2*del.first, del.second = -2*del.second;
            cb(total, del);

            ans[id] -= total.second;
        }

        if(_ == (int)cur.size() - 1) {
            fi(id, 1, Q) {
                int u = qr[id].u, v = qr[id].v, p = lca(u, v);
                ll golden = qr[id].golden, silver = qr[id].silver;

                pii total = cb(Bit.get(in[u]), Bit.get(in[v]));
                pii del = Bit.get(in[p]); del.first = -2*del.first, del.second = -2*del.second;
                cb(total, del);

                ans[id] += total.second;
            }
        }
    }

    fi(i, 1, Q) {
        int golden = qr[i].golden;
        cout << (golden - ans[i] < 0 ? -1 : golden - ans[i]) << '\n';
    }
}


 main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void solve()':
currencies.cpp:162:20: warning: unused variable 'golden' [-Wunused-variable]
  162 |                 ll golden = qr[id].golden, silver = qr[id].silver;
      |                    ^~~~~~
currencies.cpp:154:17: warning: unused variable 'u' [-Wunused-variable]
  154 |             int u = ed[i].first, v = ed[i].second;
      |                 ^
currencies.cpp:189:16: warning: unused variable 'golden' [-Wunused-variable]
  189 |             ll golden = qr[id].golden, silver = qr[id].silver;
      |                ^~~~~~
currencies.cpp:189:40: warning: unused variable 'silver' [-Wunused-variable]
  189 |             ll golden = qr[id].golden, silver = qr[id].silver;
      |                                        ^~~~~~
currencies.cpp:201:20: warning: unused variable 'golden' [-Wunused-variable]
  201 |                 ll golden = qr[id].golden, silver = qr[id].silver;
      |                    ^~~~~~
currencies.cpp:201:44: warning: unused variable 'silver' [-Wunused-variable]
  201 |                 ll golden = qr[id].golden, silver = qr[id].silver;
      |                                            ^~~~~~
currencies.cpp:183:13: warning: unused variable 'u' [-Wunused-variable]
  183 |         int u = ed[i].first, v = ed[i].second;
      |             ^
currencies.cpp: At global scope:
currencies.cpp:219:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  219 |  main() {
      |  ^~~~
currencies.cpp: In function 'void iof()':
currencies.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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