Submission #1021280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021280		underwaterkillerwhale	Two Currencies (JOI23_currencies)	C++17	100 / 100	3748 ms	126804 KiB

currencies

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rd);
}

const int N  = 1e5 + 7;
const int Mod =1e9 + 7;
const int szBL = 916;
const int INF = 2e9 + 7;
const int BASE = 137;

int n, m, Q;
int a[N];

vector<int> ke[N];
pair<int, int> edg[N];

pair<ll,ll> b[N];

int high[N], pa[N][25];
int nChild[N], in[N], Head[N], par[N], nChain = 1, chainId[N];

struct Persistent_Segment_Tree {
    int Range;
    struct Node {
        Node *lc, *rc;
        ll sum, cnt;

        Node (ll sum = 0, ll cnt = 0) : lc(nullptr), rc (nullptr), sum(sum), cnt(cnt) {};
        Node (Node *lc, Node *rc) : lc(lc), rc(rc), sum(0), cnt(0) {
            sum += lc->sum, cnt += lc->cnt;
            sum += rc->sum, cnt += rc->cnt;
        }
    }*ver[N];

    Node *build (int l, int r) {
        if (l == r) return new Node (0LL, 0LL);
        int mid = l + r >> 1;
        return new Node (build (l, mid), build (mid +1 , r));
    }

    void init (int n) {
        Range = n;
        ver[0] = build (1, Range);
    }

    Node *update (Node *cur, int l, int r, int pos, ll val) {
        if (l == r) {
            return new Node (cur->sum + val, cur->cnt + 1);
        }
        int mid = l + r >> 1;
        if (pos <= mid)
            return new Node (update (cur->lc, l, mid, pos, val), cur->rc);
        else
            return new Node (cur->lc, update (cur->rc, mid + 1, r, pos, val));
    }

    pair<ll, ll> get (Node *cur, int l, int r, int u, int v) {
        if (u > v) return mp(0, 0);
        if (l > v || r < u) return mp(0, 0);
        if (l >= u && r <= v)
            return mp(cur->sum, cur->cnt);
        int mid = l + r >> 1;
        pair<ll,ll> p1 = get(cur->lc, l, mid, u, v);
        pair<ll,ll> p2 = get(cur->rc, mid + 1, r, u, v);
        return mp(p1.fs + p2.fs, p1.se + p2.se);
    }

    void update (int pos, ll val) {
        static int nver = 0;
        ++nver;
        ver[nver] = update (ver[nver - 1], 1, Range, pos, val);
    }
    pair<ll, ll> get (int u, int v, int vr) {
        return get (ver[vr], 1, Range, u, v);
    }
}ST;

void pdfs (int u, int p) {
    nChild[u] = 1;
    pa[u][0] = par[u] = p;
    high[u] = high[p] + 1;
    rep (i, 1, 20) pa[u][i] = pa[pa[u][i - 1]][i - 1];
    iter (&v, ke[u]) {
        if (v != p) {
            pdfs(v, u);
            nChild[u] += nChild[v];
        }
    }
}

void hld (int u, int p) {
    static int time_dfs = 0;
    if (nChain != chainId[p]) Head[u] = u;
    else Head[u] = Head[p];
    chainId[u] = nChain;
    in[u] = ++time_dfs;
    int mxV = -1;
    iter (&v, ke[u]) {
        if (v != p && (mxV == -1 || nChild[v] > nChild[mxV])) {
            mxV = v;
        }
    }
//    cout << u <<" "<<Head[u] <<" "<<in[u] <<"\n";
    if (mxV != -1) hld (mxV, u);
    iter (&v, ke[u]) {
        if (v == p  || v == mxV) continue;
        ++nChain;
        hld (v, u);
    }
}

int Lca (int u, int v) {
    if (high[u] > high[v]) swap (u, v);
    int delta = high[v] - high[u];
    rep (i, 0, 20) if (bit(delta, i)) {
        v = pa[v][i];
    }
    if (v == u) return u;
    reb (i, 20, 0) {
        if (pa[v][i] != pa[u][i]) {
            v = pa[v][i];
            u = pa[u][i];
        }
    }
    return pa[u][0];
}

int Dist (int u, int v) {
    return high[u] + high[v] - 2 * high[Lca(u, v)];
}

pair<ll,ll> get (int u, int v, int ver) {
    ll sum = 0, cnt = 0;
    for (; Head[u] != Head[v]; v = par[Head[v]]) {
        if (high[Head[u]] > high[Head[v]]) swap (u, v);
        pair<ll,ll> cur = ST.get (in[Head[v]], in[v], ver);
        sum += cur.fs;
        cnt += cur.se;
//        cout << Head[v] <<" "<<v<<" "<<cur.fs<<" "<<cur.se<<"\n";
    }
    if (high[u] > high[v]) swap (u, v);
    pair<ll,ll> cur = ST.get (in[u] + 1, in[v], ver);
    sum += cur.fs;
    cnt += cur.se;
//    cout << u <<" "<<v<<" "<<cur.fs<<" "<<cur.se<<"\n";
    return mp (sum, cnt);
}

void solution () {
    cin >> n >> m >> Q;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
        edg[i] = {u, v};
    }
    pdfs (1, 0);
    hld (1, 0);
    rep (i, 1, m) {
        ll id, val;
        cin >> id >> val;
        if (par[edg[id].fs] != edg[id].se) swap(edg[id].fs, edg[id].se);
        b[i] = {edg[id].fs, val};
    }
    sort (b + 1, b + 1 + m, [] (pair<ll,ll> A, pair<ll,ll> B) { return A.se < B.se; });
    ST.init(n);
    rep (i, 1, m) {
        ST.update (in[b[i].fs], b[i].se);
//        cout << in[b[i].fs]<<","<<b[i].se<<" "<<ST.get(
    }
    rep (i, 1, Q) {
        int u, v;
        ll X, Y;
        cin >> u >> v >> X >> Y;
        int lf = 0, rt = m;
        while (lf < rt) {
            int mid = lf + rt + 1 >> 1;
            if (get(u, v, mid).fs <= Y) lf =  mid;
            else rt = mid - 1;
        }
        pair<ll,ll> cur = get(u, v, lf);
//        cout << lf <<" "<<cur.fs<<" "<<cur.se<<"\n";
        if (get(u, v, m).se - cur.se <= X) {
            cout << X - (get(u, v, m).se  - cur.se) <<"\n";
        }
        else cout << -1 <<"\n";

    }
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
1 2
*/

Compilation message (stderr)

currencies.cpp: In member function 'Persistent_Segment_Tree::Node* Persistent_Segment_Tree::build(int, int)':
currencies.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~
currencies.cpp: In member function 'Persistent_Segment_Tree::Node* Persistent_Segment_Tree::update(Persistent_Segment_Tree::Node*, int, int, int, long long int)':
currencies.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
currencies.cpp: In member function 'std::pair<long long int, long long int> Persistent_Segment_Tree::get(Persistent_Segment_Tree::Node*, int, int, int, int)':
currencies.cpp:81:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mid = l + r >> 1;
      |                   ~~^~~
currencies.cpp: In function 'void solution()':
currencies.cpp:197:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  197 |             int mid = lf + rt + 1 >> 1;
      |                       ~~~~~~~~^~~

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