Submission #1291839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291839		nguyenkhangninh99	Two Currencies (JOI23_currencies)	C++20	100 / 100	903 ms	54568 KiB

currencies

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e5 + 5;
vector<int> g[maxn];
pair<int, int> edge[maxn], sta[maxn];
vector<int> res[maxn];

int s[maxn], t[maxn], w[maxn];
int G[maxn], S[maxn], bit[maxn];
void update(int p, int val){
    for(; p < maxn; p += p & -p) bit[p] += val;
}
int get(int p){
    int res = 0;
    for(; p; p -= p & -p) res += bit[p];
    return res;
}

//for HLD
int nxt[maxn], head[maxn], sz[maxn], par[maxn], h[maxn];
int tin[maxn], out[maxn], timedfs;

void dfs(int u, int p){
    sz[u] = 1;

    for(int v: g[u]){
        if(v == p) continue;
        par[v] = u;
        h[v] = h[u] + 1;
        dfs(v, u);

        sz[u] += sz[v];
        if(sz[nxt[u]] < sz[v]) nxt[u] = v;
    }
}

void hld(int u, int p, int cur){
    tin[u] = ++timedfs;
    head[u] = cur;

    if(nxt[u]) hld(nxt[u], u, cur);

    for(int v: g[u]){
        if(v == p || v == nxt[u]) continue;
        hld(v, u, v);
    }

    out[u] = timedfs;
}
int path(int u, int v){
    int ans = 0;
    while(head[u] != head[v]){
        if(h[head[u]] < h[head[v]]) swap(u, v);
        ans += get(tin[u]) - get(tin[head[u]] - 1);
        u = par[head[u]];
    }
    if(h[u] > h[v]) swap(u, v);
    ans += get(tin[v]) - get(tin[u]);

    return ans;
}

//for PBS
int L[maxn], R[maxn], ans[maxn];
vector<int> query[maxn];

signed main(){ 
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, -1);
    hld(1, -1, 1);

    //di qua ton 1 G hoac c S
    for(int i = 1; i <= m; i++){
        int id, c; cin >> id >> c;

        auto [u, v] = edge[id];
        if(h[u] > h[v]) swap(u, v);
        sta[i] = {c, v};
    }   

    //sort lai c
    sort(sta + 1, sta + 1 + m);

    //tinh so G toi da giu lai duoc
    for(int i = 1; i <= q; i++) cin >> s[i] >> t[i] >> G[i] >> S[i];

    for(int i = 1; i <= q; i++) L[i] = 1, R[i] = m;
    for(int loop = 1; loop <= 20; loop++){
        memset(bit, 0, sizeof(bit));
        for(int i = 1; i <= q; i++) if(L[i] <= R[i]) query[(L[i] + R[i]) / 2].push_back(i);
        for(int mid = 1; mid <= m; mid++){
            auto [cost, u] = sta[mid];
            update(tin[u], cost);

            for(int i: query[mid]){
                if(path(s[i], t[i]) <= S[i]) L[i] = mid + 1, ans[i] = mid;
                else R[i] = mid - 1;
            }
            query[mid].clear();
        }
    }

    for(int i = 1; i <= q; i++) res[ans[i]].push_back(i);

    memset(bit, 0, sizeof(bit));
    for(int i = 1; i <= m; i++){
        update(tin[sta[i].second], 1);

        for(int v: res[i]) w[v] = path(s[v], t[v]); //sl cua hang di qua nhieu nhat bang silver
    }

    for(int i = 1; i <= q; i++){
        int cost = path(s[i], t[i]);
        if(cost - w[i] <= G[i]) cout << G[i] - cost + w[i] << '\n';
        else cout << -1 << '\n';
    }
}

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