Submission #1281896

#TimeUsernameProblemLanguageResultExecution timeMemory
1281896hssaan_arifTwo Currencies (JOI23_currencies)C++20
10 / 100
5092 ms34460 KiB
// #include <me>
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , m , q , s , t , x , y , u , v ;
vector<int> lis[N] , cost[N];
vector<pair<int,int>> w;
map<pair<int,int> , int> ch;

bool dfs(int u , int par , int ta){
    if (u == ta){
        return 1;
    }
    bool p = 0;
    for (int v : lis[u]){
        if (v != par){
            if (dfs(v , u , t)){
                w.pb({v,u});
                p = 1;
            }
        }
    }
    return p;
}

void solve(){
    cin >> n >> m >> q;
    map<pair<int,int> , int> ch;
    for (int i = 1 ; i < n ; i++){
        cin >> u >> v;
        lis[u].pb(v);
        lis[v].pb(u);
        ch[{u,v}] = i;
        ch[{v,u}] = i;
    }
    // dfs(1 , 1);
    for (int i = 1 ; i <= m ; i++){
        cin >> u >> v;
        cost[u].pb(v);
    }
    while(q--){
        cin >> s >> t >> x >> y;
        w.clear();
        dfs(s , s , t);
        vector<int> cs;
        for (auto i : w){
            for (auto j : cost[(ch[{i.fi,i.se}])]){
                cs.pb(j);
            }
            
        }
        sort(cs.begin(),cs.end());
        for (int i = 0 ; i < cs.size() ; i++){
            if (cs[i] > y){
                x--;
            }else{
                y -= cs[i];
            }
        }
        if (x < 0){
            cout << -1 << endl;
            continue;
        }
        cout << x << endl;
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...