Submission #950115

#	Time	Username	Problem	Language	Result	Execution time	Memory
950115		Abdalaziz_Alshami	Two Currencies (JOI23_currencies)	C++17	28 / 100	464 ms	51152 KiB

currencies

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,lo=21;
int an[N][lo],dis[N],cost[N];
map<pair<int,int>,int>mp;
pair<int,int> ed[N];
vector<int> a[N];
void dfs(int x,int p)
{
    an[x][0]=p;
    dis[x]=dis[p]+1;
    cost[x]=mp[{x,p}]+cost[p];
    for(int i=1;i<lo;i++) an[x][i]=an[an[x][i-1]][i-1];
    for(auto i:a[x]) if(i!=p) dfs(i,x);
}
int lca(int x,int y)
{
    if(dis[x]>dis[y]) swap(x,y);
    for(int i=lo-1;i>=0;i--)
        if(dis[an[y][i]]>=dis[x]) y=an[y][i];
    if(x==y) return x;
    for(int i=lo-1;i>=0;i--)
        if(an[x][i]!=an[y][i])
            x=an[x][i],y=an[y][i];
    return an[x][0];
}
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};
    }
    int val;
    for(int i=0;i<m;i++)
    {
        int p; cin>>p>>val;
        auto [f,s]=ed[p];
        mp[{f,s}]++;
        mp[{s,f}]++;
    }
    dis[0]=-1; dfs(1,0);
    while(q--)
    {
        int x,y,g,s; cin>>x>>y>>g>>s;
        int node=lca(x,y);
        int ss=cost[x]+cost[y]-2*cost[node];
        ss-=(int)(s/val); ss=max(ss,0ll);
        g-=ss;
        if(g<0) cout<<-1<<endl;
        else cout<<g<<endl;
    }
}

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