Submission #897744

#	Time	Username	Problem	Language	Result	Execution time	Memory
897744		Mr_Husanboy	Two Currencies (JOI23_currencies)	C++17	10 / 100	5085 ms	19100 KiB

currencies

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){
    return a.size();
}

void solve(){
    int n, m, q; cin >> n >> m >> q;

    vector<vector<pair<int,int>>> g(n);

    for(int i = 0; i < n - 1; i ++){
        int u, v; cin >> u >> v;
        u --; v --;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }

    vector<vector<int>> way(n - 1);
    for(int i = 0; i < m; i ++){
        int id, sil; cin >> id >> sil;
        id --; way[id].push_back(sil);
    }

    vector<int> st(q), en(q), gold(q);
    vector<ll> silver(q);

    for(int i = 0; i < q; i ++){
        cin >> st[i] >> en[i] >> gold[i] >> silver[i];
        st[i] --; en[i] --;
    }

    auto brute = [&]{

        vector<int> par(n), wayid(n);
        auto dfs = [&](auto &dfs, int i, int p = -1, int r = -1)->void{
            par[i] = p;
            wayid[i] = r;
            for(auto [u, id] : g[i]){
                if(u == p) continue;
                dfs(dfs, u, i, id);
            }
        };

        for(int i = 0; i < q; i ++){
            dfs(dfs, st[i]);

            vector<ll> pay;

            int cur = en[i];
            while(wayid[cur] != -1){
                //cout << wayid[cur] + 1 << ' ';
                for(auto u : way[wayid[cur]]){
                    pay.push_back(u);
                    //cout << u << ' ';
                }
                cur = par[cur];
            }
            if(pay.empty()){
                cout << gold[i] << '\n'; continue;
            }
            sort(all(pay));
            for(int j = 1; j < len(pay); j ++){
                pay[j] += pay[j - 1];
            }

            int rem = gold[i] - len(pay) + (upper_bound(all(pay), silver[i]) - pay.begin());
            cout << max(-1, rem) << '\n';
        }
    };

    brute();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int testcases = 1;

    #ifdef Tests
    cin >> testcases;
    #endif

    while(testcases --){
        solve();
        if(testcases) cout << '\n';
        #ifdef LOCAL
        else
        cout << '\n';
        cout << "________________________" << endl;
        #endif
    }
    #ifdef LOCAL
    cout << "done" << endl;
    #endif
    return 0;
}

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