Submission #950051

#	Time	Username	Problem	Language	Result	Execution time	Memory
950051		Abdalaziz_Alshami	Two Currencies (JOI23_currencies)	C++17	10 / 100	5015 ms	35136 KiB

currencies

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,lo=21;
int pa[N],dis[N];
map<pair<int,int>,vector<int>>cost;
pair<int,int> ed[N];
vector<int> a[N];
void dfs(int x,int p)
{
    pa[x]=p;
    dis[x]=dis[p]+1;
    for(auto i:a[x]) if(i!=p) dfs(i,x);
}
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m,q; cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int u,v; cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
        ed[i]={u,v};
    }
    for(int i=0;i<m;i++)
    {
        int p,c; cin>>p>>c;
        auto [f,s]=ed[p];
        cost[{f,s}].push_back(c);
        cost[{s,f}].push_back(c);
    }
    dis[0]=-1; dfs(1,0);
    while(q--)
    {
        int x,y,g,s; cin>>x>>y>>g>>s;
        vector<int>v;
        if(dis[x]>dis[y]) swap(x,y);
        while(dis[y]!=dis[x]) {
            for(auto i:cost[{y,pa[y]}]) v.push_back(i);
                y=pa[y];
        }
        while(x!=y)
        {
            for(auto i:cost[{y,pa[y]}]) v.push_back(i);
            for(auto i:cost[{x,pa[x]}]) v.push_back(i);
            x=pa[x]; y=pa[y];
        }
        sort(v.begin(),v.end());
        int ss=v.size();
        for(auto i:v) if(s-i>=0) s-=i,ss--;
        g-=ss;
        if(g<0) cout<<-1<<endl;
        else cout<<g<<endl;
    }
}

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