Submission #1217415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217415		BuiDucManh123	Two Currencies (JOI23_currencies)	C++20	0 / 100	5 ms	9800 KiB

currencies

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define taskname ""
using namespace std;
const int MAXN = 200000 + 5;
const int LOG = 20;
int n, m, q;
vector<pair<int,int>> adj[MAXN];
vector<int> costsOnEdge[MAXN];
int parentUp[LOG][MAXN];
int depthArr[MAXN];
int rootPST[MAXN];
struct Node { int l, r; int cnt; ll sum; } seg[5000000];
int nxtNode = 1;
vector<int> comp;
int K;

int updatePST(int prev, int l, int r, int pos){
    int cur = nxtNode++;
    seg[cur] = seg[prev];
    seg[cur].cnt += 1;
    seg[cur].sum += comp[pos-1];
    if(l < r){
        int mid = (l + r) >> 1;
        if(pos <= mid) seg[cur].l = updatePST(seg[prev].l, l, mid, pos);
        else seg[cur].r = updatePST(seg[prev].r, mid+1, r, pos);
    }
    return cur;
}

int dfs_build(int u, int p){
    parentUp[0][u] = p;
    for(auto &pr : adj[u]){
        int v = pr.fi;
        int ei = pr.se;
        if(v == p) continue;
        depthArr[v] = depthArr[u] + 1;
        int curRoot = rootPST[u];
        for(int c : costsOnEdge[ei]){
            int idx = int(lower_bound(comp.begin(), comp.end(), c) - comp.begin()) + 1;
            curRoot = updatePST(curRoot, 1, K, idx);
        }
        rootPST[v] = curRoot;
        dfs_build(v, u);
    }
    return 0;
}

int lca(int u, int v){
    if(depthArr[u] < depthArr[v]) swap(u, v);
    int diff = depthArr[u] - depthArr[v];
    for(int i = 0; i < LOG; i++){
        if(diff & (1<<i)) u = parentUp[i][u];
    }
    if(u == v) return u;
    for(int i = LOG-1; i >= 0; i--){
        if(parentUp[i][u] != parentUp[i][v]){
            u = parentUp[i][u];
            v = parentUp[i][v];
        }
    }
    return parentUp[0][u];
}

ll cntNode(int x){ return seg[x].cnt; }
ll sumNode(int x){ return seg[x].sum; }

ll querySilver(int ru, int rv, int rlca, ll &Y, int l, int r){
    if(!ru && !rv && !rlca) return 0;
    if(l == r){
        ll cntLeft = cntNode(seg[ru].l) + cntNode(seg[rv].l) - 2LL*cntNode(seg[rlca].l);
        ll cost = comp[l-1];
        ll take = min(cntLeft, Y / cost);
        Y -= take * cost;
        return take;
    }
    int mid = (l + r) >> 1;
    int lu = seg[ru].l, lv = seg[rv].l, llca = seg[rlca].l;
    ll cntLeft = cntNode(lu) + cntNode(lv) - 2LL*cntNode(llca);
    ll sumLeft = sumNode(lu) + sumNode(lv) - 2LL*sumNode(llca);
    if(sumLeft <= Y){
        Y -= sumLeft;
        ll takeLeft = cntLeft;
        int ruR = seg[ru].r, rvR = seg[rv].r, rlcaR = seg[rlca].r;
        return takeLeft + querySilver(ruR, rvR, rlcaR, Y, mid+1, r);
    } else {
        int ruL = seg[ru].l, rvL = seg[rv].l, rlcaL = seg[rlca].l;
        return querySilver(ruL, rvL, rlcaL, Y, l, mid);
    }
}

int main(){
    if(fopen(taskname".inp","r")){
        freopen(taskname".inp","r", stdin);
        freopen(taskname".out","w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> q;
    vector<pair<int,int>> edges(n);
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
        edges[i] = {u,v};
    }
    vector<pair<int,int>> checkpoints(m+1);
    for(int j = 1; j <= m; j++){
        int pj, cj;
        cin >> pj >> cj;
        checkpoints[j] = {pj, cj};
        costsOnEdge[pj].pb(cj);
        comp.pb(cj);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    K = comp.size();
    rootPST[1] = 0;
    depthArr[1] = 0;
    dfs_build(1, 1);
    for(int i = 1; i < LOG; i++){
        for(int u = 1; u <= n; u++){
            parentUp[i][u] = parentUp[i-1][ parentUp[i-1][u] ];
        }
    }
    while(q--){
        int s,t;
        ll X,Y;
        cin >> s >> t >> X >> Y;
        int w = lca(s,t);
        ll totalCnt = cntNode(rootPST[s]) + cntNode(rootPST[t]) - 2LL*cntNode(rootPST[w]);
        ll remY = Y;
        ll silverUsed = querySilver(rootPST[s], rootPST[t], rootPST[w], remY, 1, K);
        ll goldSpent = totalCnt - silverUsed;
        if(goldSpent > X) cout << -1 << "\n";
        else cout << (X - goldSpent) << "\n";
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(taskname".inp","r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(taskname".out","w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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