제출 #1265539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265539		spetr	Two Currencies (JOI23_currencies)	C++20	10 / 100	5094 ms	39256 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;


}

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

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

    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;
        a--;
        price[edges[a]].push_back(b);
        price[{edges[a].second,edges[a].first}].push_back(b);
    }

    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";
        }

    }




    return 0;
}

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