제출 #831571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831571		alvingogo	Two Currencies (JOI23_currencies)	C++17	100 / 100	1109 ms	51276 KiB

currencies

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct ST{
    vector<int> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int l,int r,int a){
        if(L==l && r==R){
            st[v]+=a;
            return;
        }
        int m=(L+R)/2;
        if(r<=m){
            update(2*v+1,L,m,l,r,a);
        }
        else if(l>m){
            update(2*v+2,m+1,R,l,r,a);
        }
        else{
            update(2*v+1,L,m,l,m,a);
            update(2*v+2,m+1,R,m+1,r,a);
        }
    }
    int query(int v,int L,int R,int t){
        if(L==R){
            return st[v];
        }
        int m=(L+R)/2;
        if(t<=m){
            return st[v]+query(2*v+1,L,m,t);
        }
        else{
            return st[v]+query(2*v+2,m+1,R,t);
        }
    }
}st;
struct no{
    vector<int> ch;
    int in,out;
    int as[18]={0};
};
int cnt=0;
vector<no> v;
void dfs(int r,int f){
    cnt++;
    v[r].as[0]=f;
    v[r].in=cnt;
    for(auto h:v[r].ch){
        if(h!=f){
            dfs(h,r);
        }
    }
    v[r].out=cnt;
}
bool as(int a,int b){
    return v[a].in<=v[b].in && v[a].out>=v[b].out;
}
int lca(int a,int b){
    if(as(a,b)){
        return a; 
    }
    for(int i=17;i>=0;i--){
        if(!as(v[a].as[i],b)){
            a=v[a].as[i];
        }
    }
    return v[a].as[0];
}
vector<pair<int,int> > z;
struct QU{
    int a,b,l;
    int c,d;
};
vector<QU> x;
int n;
vector<vector<int> > rf;
void cd(int l,int r,vector<int>& a){
    if(a.empty()){
        return;
    }
    if(l==r){
        rf[l]=a;
        return;
    }
    int m=(l+r)/2;
    for(int i=l;i<=m;i++){
        st.update(0,0,n,v[z[i].sc].in,v[z[i].sc].out,z[i].fs);
    }
    vector<int> b,c;
    for(auto h:a){
        int a=st.query(0,0,n,v[x[h].a].in)+st.query(0,0,n,v[x[h].b].in)-2*st.query(0,0,n,v[x[h].l].in);
        if(a<=x[h].d){
            c.push_back(h);
        }
        else{
            b.push_back(h);
        }
    }
    cd(m+1,r,c);
    for(int i=l;i<=m;i++){
        st.update(0,0,n,v[z[i].sc].in,v[z[i].sc].out,-z[i].fs);
    }
    cd(l,m,b);
}
signed main(){
    AquA;
    int m,q;
    cin >> n >> m >> q;
    v.resize(n);
    st.init(n+1);
    vector<pair<int,int> > eg(n);
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        eg[i]={a,b};
        v[a].ch.push_back(b);
        v[b].ch.push_back(a);
    }
    dfs(0,0);
    for(int i=1;i<18;i++){
        for(int j=0;j<n;j++){
            v[j].as[i]=v[v[j].as[i-1]].as[i-1];
        }
    }
    for(auto &h:eg){
        if(v[h.fs].as[0]!=h.sc){
            swap(h.fs,h.sc);
        }
    }
    z.resize(m);
    for(int i=0;i<m;i++){
        int a;
        cin >> a >> z[i].fs;
        z[i].sc=eg[a].fs;
    }
    sort(z.begin(),z.end());
    x.resize(q);
    for(int i=0;i<q;i++){
        cin >> x[i].a >> x[i].b >> x[i].c >> x[i].d;
        x[i].a--;
        x[i].b--;
        x[i].l=lca(x[i].a,x[i].b);
    }
    vector<int> sw(q);
    iota(sw.begin(),sw.end(),0);
    rf.resize(m+1);
    cd(0,m,sw);
    ST st2;
    st2.init(n+1);
    vector<int> ans(q);
    for(int i=m;i>=0;i--){
        if(i!=m){
            st2.update(0,0,n,v[z[i].sc].in,v[z[i].sc].out,1);
        }
        for(auto h:rf[i]){
            ans[h]=x[h].c-(st2.query(0,0,n,v[x[h].a].in)+st2.query(0,0,n,v[x[h].b].in)-2*st2.query(0,0,n,v[x[h].l].in));
        }
    }
    for(auto h:ans){
        if(h<0){
            cout << -1 << '\n';
        }
        else{
            cout << h << "\n";
        }
    }
    return 0;
}

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