Submission #1298904

#TimeUsernameProblemLanguageResultExecution timeMemory
1298904khoavn2008Two Currencies (JOI23_currencies)C++17
0 / 100
8 ms9792 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
const ll MOD = 1e9 + 7, N = 2e5 + 36, LOG = 18;
const int INF = 1e9 + 36;
ll n,m,q,par[N],high[N];
vector<int> adj[N];
vector<ll> S[N];
pair<int,int> edge[N];
void dfs(int u){
    for(int v : adj[u])if(v != par[u]){
        high[v] = high[u] + 1;
        par[v] = u;
        dfs(v);
    }
}
int main(){
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    FOR(i,1,n-1){
        int u,v;cin>>u>>v;
        edge[i] = {u, v};
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1);
    FOR(i,1,m){
        ll p,c;cin>>p>>c;
        auto [u, v] = edge[p];
        if(high[u] > high[v])S[u].pb(c);
        else S[v].pb(c);
    }
    FOR(i,1,q){
        ll s,t,x,y;cin>>s>>t>>x>>y;
        vector<ll> vec;
        if(high[s] < high[t])swap(s, t);
        ll sum = 0;
        while(high[s] < high[t]){
            for(ll v : S[s])vec.pb(v),sum += v;
            s = par[s];
        }
        while(s != t){
            for(ll v : S[s])vec.pb(v),sum += v;
            for(ll v : S[t])vec.pb(v),sum += v;
            s = par[s];
            t = par[t];
        }
        sort(all(vec), greater<ll>());
        for(ll v : vec){
            if(sum <= y)break;
            x--;
            sum -= v;
        }
        if(x < 0)cout<<-1<<endl;
        else cout<<x<<endl;
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...