Submission #916373

#	Time	Username	Problem	Language	Result	Execution time	Memory
916373		owoovo	Two Currencies (JOI23_currencies)	C++17	100 / 100	787 ms	37612 KiB

currencies

#include<bits/stdc++.h>
#define ll long long
#define F first 
#define S second 
using namespace std;
struct bit{
    ll ori[200050]={};
    void modify(int x,int pos){
        while(pos<200030){
            ori[pos]+=x;
            pos+=pos&(-pos);
        }
        return;
    }
    ll q(int x){
        ll ans=0;
        while(x){
            ans+=ori[x];
            x-=x&(-x);
        }
        return ans;
    }
    ll query(int l,int r){
        return q(r)-q(l);
    }
}cont,sum;
struct query{
    ll u,v,x,y,id;
}qu[100010];
vector<int> e[100010];
vector<pair<int,int>> eg;
vector<pair<ll,int>> edge;
int in[100010],out[100010],f[100010][20],depth[100010],cnt,n,m,q,nowr;
ll ans[100010];
void dfs(int now,int last){
    in[now]=++cnt;
    f[now][0]=last;
    depth[now]=depth[last]+1;
    for(auto x:e[now]){
        if(x==last)continue;
        dfs(x,now);
    }
    out[now]=++cnt;
    return;
}
int lca(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=18;i>=0;i--){
        if(depth[u]-(1<<i)>=depth[v]){
            u=f[u][i];
        }
    }
    if(u==v){
        return u;
    }
    for(int i=18;i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];
}

void add(int id,int c){
    ll val=edge[id].F,v=edge[id].S;
    cont.modify(c,in[v]);
    cont.modify(-c,out[v]);
    sum.modify(val*c,in[v]);
    sum.modify(-val*c,out[v]);
}
void answer(int id){
    ll u=qu[id].u,v=qu[id].v;
    ans[id]=cont.query(in[lca(u,v)],in[u])+cont.query(in[lca(u,v)],in[v]);
    return;
}
bool check(int id){
    ll u=qu[id].u,v=qu[id].v;
    return sum.query(in[lca(u,v)],in[u])+sum.query(in[lca(u,v)],in[v])<=qu[id].y;
}
void tox(int x){
    while(nowr<x)add(++nowr,1);
    while(nowr>x)add(nowr--,-1);
    return;
}
void tbs(int l,int r,vector<int>* q){
    if((*q).size()==0)return;
    if(l==r){
        tox(l);
        for(auto id:(*q)){
            answer(id);
        }
        return;
    }
    int m=(l+r+1)/2;
    tox(m);
    vector<int> L;
    vector<int> R;
    for(auto id:(*q)){
        if(check(id)){
            R.push_back(id);
        }else{
            L.push_back(id);
        }
    }
    tbs(l,m-1,&L);
    tbs(m,r,&R);
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        eg.push_back(make_pair(a,b));
        e[a].push_back(b);
        e[b].push_back(a);
    }
    cnt=1;
    nowr=0;
    dfs(1,1);
    for(int i=1;i<=18;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    for(int i=0;i<m;i++){
        ll p,c;
        cin>>p>>c;
        p--;
        int v=eg[p].F;
        if(f[v][0]!=eg[p].S)v=eg[p].S;
        edge.push_back(make_pair(c,v));
    }
    edge.push_back(make_pair(0,0));
    sort(edge.begin(),edge.end());
    vector<int> qur;
    for(int i=0;i<q;i++){
        cin>>qu[i].u>>qu[i].v>>qu[i].x>>qu[i].y;
        qu[i].id=i;
        qur.push_back(i);
    }
    tbs(0,m,&qur);
    tox(m);
    for(int i=0;i<q;i++){
        int u=qu[i].u,v=qu[i].v;
        cout<<max(-1ll,ans[i]+qu[i].x-cont.query(in[lca(u,v)],in[u])-cont.query(in[lca(u,v)],in[v]))<<"\n";
    }
    return 0;
}

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