Submission #1185272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185272		ezzzay	Two Currencies (JOI23_currencies)	C++20	0 / 100	10 ms	8004 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int par[32][N],p[N],c[N],dst[N];
vector<int>ans;
vector<int>v[N];
int lvl[N];
int n,m,q;
int hs[N];
map<pair<int,int>,int>mp;
void dfs(int a, int p){
    lvl[a]=lvl[p]+1;
    par[0][a]=p;
    for(auto b:v[a]){
        if(p==b)continue;
        dst[b]=dst[a]+mp[{min(a,b),max(a,b)}];
        dfs(b,a);
    }
}
void binlift(){
    dfs(1,0);
    for(int i=1;i<=30;i++){
        for(int j=1;j<=n;j++){
            par[i][j]=par[i-1][ par[i-1][j] ];
        }
    }
}
int lca(int a, int b){
    if(lvl[b]>lvl[a])swap(a,b);
    int x=lvl[a]-lvl[b];
    for(int i=0;i<=30;i++){
        if(x &(1<<i)){
            a=par[i][a];
        }
    }
    x=0;
    int u=a,g=b;
    if(a==b){
        return a;
    }
    for(int i=30;i>=0;i--){
        if(par[i][u]!=par[i][g]){
            u=par[i][u];
            g=par[i][g];
        }
    }
    u=par[0][u];
    return u;
}
signed main(){
    cin>>n>>m>>q;
    vector<pair<int,int>>rt;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
        rt.pb({min(a,b),max(a,b)});
    }
    for(int i=1;i<=m;i++){
        cin>>p[i]>>c[i]; 
        mp[rt[p[i]-1]]+=1;
    }
    binlift();
    while(q--){
        int x,y,g,s;
        cin>>x>>y>>g>>s;
        int h=lca(x,y);
        int k=dst[x]+dst[y]-dst[h]*2;
        s= s/c[1];
        g-= max(k-s,0);
        g=max(g,-1);
        ans.pb(g);
    }
    for(auto a:ans)cout<<a<<endl;
}

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