Submission #1222109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222109		Aviansh	Two Currencies (JOI23_currencies)	C++20	10 / 100	5095 ms	25616 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<int>checks;

void dfs(int st, vector<array<int,2>>g[], vector<int>costs[], vector<int>&curr, int tar, int p){
    if(st==tar){
        for(int i : curr){
            checks.push_back(i);
        }
        return;
    }
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        for(int i : costs[e[1]]){
            curr.push_back(i);
        }
        dfs(e[0],g,costs,curr,tar,st);
        for(int i : costs[e[1]]){
            assert(curr.size());
            curr.pop_back();
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<array<int,2>>g[n];
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back({b,i});
        g[b].push_back({a,i});
    }
    vector<int>costs[n-1];
    for(int i = 0;i<m;i++){
        int p,c;
        cin >> p >> c;
        p--;
        costs[p].push_back(c);
    }
    for(int i = 0;i<n-1;i++){
        if(costs[i].size())
            sort(costs[i].begin(),costs[i].end());
    }
    while(q--){
        int s,t,x,y;
        cin >> s >> t >> x >> y;
        s--;t--;
        checks.clear();
        vector<int>temp;
        dfs(s,g,costs,temp,t,-1);
        if(checks.size()!=0){
            sort(checks.begin(),checks.end());
            x-=checks.size();
            for(int i : checks){
                if(y-i>=0){
                    y-=i;
                    x++;
                }
                else{
                    break;
                }
            }
        }
        if(x<0){
            cout << -1 << "\n";
        }
        else{
            cout << x << "\n";
        }
    }
    return 0;
}

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