Submission #1265631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265631		spetr	Two Currencies (JOI23_currencies)	C++20	38 / 100	332 ms	84088 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

bool find_path(ll x, ll p, ll y, vll& graf, map<pl,vl>& prices, vl& res){
    if (x == y){
        return true;
    }
    for (ll v : graf[x]){
        if (v != p){
            bool end = find_path(v, x, y, graf, prices, res);
            if (end){
                for (ll r : prices[{x, v}]){
                    res.push_back(r);
                }
                return true;
            }
        }

    }
    return false;


}

void dfs(ll x, ll p, ll d, vll& graf, vl& depths, vector<vector<pl>>& lca, map<pl,vl>& prices){
    depths[x] = d;
    for (ll v : graf[x]){
        if (v != p){
            ll i = 0;
            ll pos = x;
            lca[v].push_back({prices[{x, v}].size(), x});
            while (lca[pos].size() > i){
                lca[v].push_back({lca[v][i].first + lca[pos][i].first, lca[pos][i].second});
                pos = lca[pos][i].second;
                i++;
            }
            dfs(v, x, d + 1, graf, depths, lca, prices);
            

        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n,m,q;
    cin >> n >> m >> q;
    ll p;

    vll graf (n);
    map<pl,vl> price;
    vector<pl> edges;

    for (ll i = 0; i < n-1; i++){
        ll a,b;
        cin >> a >> b;
        a--; b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
        edges.push_back({a,b});
    }

    for (ll i = 0; i < m; i++){
        ll a,b;
        cin >>a >>b;
        p = b;
        a--;
        price[edges[a]].push_back(b);
        price[{edges[a].second,edges[a].first}].push_back(b);
    }

    if (n <= 2000 && q <= 2000 && m <= 2000){
    while (q--){
        ll a,b,x,y;
        cin >>a >> b >> x >> y;
        a--;b--;
        vl res;
        res.clear();
        find_path(a, -1, b, graf, price, res);
        sort(res.begin(), res.end());

        ll i = 0;
        while (i < res.size()&& y >= res[i]){
            y -= res[i];
            i++;
        }

        if (res.size()-i > x){
            cout << "-1\n";
        }
        else{
            cout << x - (res.size()-i) << "\n";
        }

    }
    }
    else{
    
    vl depths(n);
    vector<vector<pl>> lca (n);
    dfs(0, -1, 0, graf, depths, lca, price);
    
    while (q--){
        ll a,b,x,y;
        cin >>a >> b >> x >> y;
        a--;b--;

        ll suma = 0;
        if (depths[a] < depths[b]) swap(a,b);
        ll pos = lca[a].size();
        while (pos >= 0 && depths[a] > depths[b]){
            if (pos < lca[a].size() && depths[lca[a][pos].second] >= depths[b]){
                suma += lca[a][pos].first;
                a = lca[a][pos].second;
            }
            pos--;
        }
        pos = lca[a].size();
        while (pos >= 0 && a != b){
            if (pos < lca[a].size() && lca[a][pos].second != lca[b][pos].second){
                suma += lca[a][pos].first + lca[b][pos].first;
                a = lca[a][pos].second;
                b = lca[b][pos].second;
            }
            pos--;
        }
        if (a != b){
            suma += lca[a][0].first + lca[b][0].first;
        }

        if (p == 0){
            cout << x << "\n";
        }
        else if (x < suma - (y/p)){
            cout << "-1\n";
        }
        else{
            ll ans = x - max(0ll, suma- y/p);
            cout << ans <<"\n";
        }

    }
    }




    return 0;
}

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