Submission #964957

#	Time	Username	Problem	Language	Result	Execution time	Memory
964957		YassirSalama	Two Currencies (JOI23_currencies)	C++17	100 / 100	3613 ms	115092 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
#define int ll
using ull=unsigned long long;
using ll=long long;
using pii=pair<int,int>;
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mxn=1e5+100;
const int lgn=20;
vector<int> v[mxn];
int depth[mxn];
int up[mxn][lgn+1];
int top[mxn];
int pos[mxn];
int BIT1[mxn];
int BIT2[mxn];
int sum[mxn];
int ans[mxn];
int nm[mxn];
int sz[mxn];
map<pii,int> mp,mp1,mp2;
map<int,pii> mp3;
vector<tuple<int,int,int>> f;
vector<vector<int>> queries;
int n,m,q;
void add(int i,int x){
    i++;
    while(i<mxn){
        BIT1[i]+=x;
        BIT2[i]+=(x>0?1:-1);
        i+=i&-i;
    }
}
pii qq(int i){
    i++;
    int ans1=0,ans2=0;
    while(i){
        ans1+=BIT1[i];
        ans2+=BIT2[i];
        i-=i&-i;
    }
    return {ans1,ans2};
}
pii s(int l,int r){
    if(l>r) return {0,0};
    pii a=qq(l-1),b=qq(r);
    return {b.F-a.F,b.S-a.S};
}
void dfs(int node,int par){
    depth[node]=depth[par]+1;
    up[node][0]=par;
    for(int i=1;i<=lgn;i++){
        up[node][i]=up[up[node][i-1]][i-1];
    }
    sz[node]=1;
    for(auto x:v[node]){
        if(x==par) continue;
        dfs(x,node);
        sz[node]+=sz[x];
    }
}
int LCA(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    int d=depth[a]-depth[b];
    for(int i=lgn;i>=0;i--){
        if(d&(1LL<<i)) a=up[a][i];
    }
    if(a==b) return a;
    for(int i=lgn;i>=0;i--){
        if(up[a][i]==up[b][i]) continue;
        a=up[a][i];
        b=up[b][i];
    }
    return up[a][0];
}
int c=1;
void HLD(int node,int par,int cID){
   top[node]=cID;
   pos[node]=c;
   c++;
   int bst=-1;
   int b=0;
   for(auto x:v[node]){
       if(x==par) continue;
       if(bst<sz[x]){
           bst=sz[x];
           b=x;
       }
   }
   if(bst!=-1){
       HLD(b,node,cID);
   }
   for(auto x:v[node]){
       if(x==par) continue;
       if(x==b) continue;
       HLD(x,node,x);
   }
}
pii query(int u,int v){
    pair<int,int> ans(0,0);
    int vv=v;
    while(top[u]!=top[v]){
        int l=top[v];
        l=pos[l];
        l++;
        int r=pos[v];
        pii a=s(l,r);
        ans.F+=a.F;
        ans.S+=a.S;
        v=top[v];
        if(mp1.count({up[v][0],v})){
            ans.F+=mp1[{up[v][0],v}];
            ans.S+=mp2[{up[v][0],v}];
        }
        v=up[v][0];
    }
    int l=u;
    l=pos[u];
    l++;
    int r=pos[v];
    pii a=s(l,r);
    // if(u==1&&v==7){
    //     dbg(l,r,u,top[v],a.F,a.S)
    // }
    ans.F+=a.F;
    ans.S+=a.S;
    return ans;
}
void bs(int l,int r,vector<vector<int>> &queries){
    mp1.clear();
    mp2.clear();
    // dbg(l,r)
    if(queries.empty()) return;
    vector<vector<int>> ok,nok;
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++){
        auto [c,a,b]=f[i];
        if(up[a][0]==b) swap(a,b);
        add(pos[b],c);
        mp1[{a,b}]+=c;
        mp2[{a,b}]++;
    }
    for(auto x:queries){
        pii ans(0,0);
        int L=LCA(x[0],x[1]);
        pii a=query(L,x[0]),b=query(L,x[1]);
        ans.F=a.F+b.F;
        ans.S=a.S+b.S;
        // if(x[4]==1){
        //     dbg(l,mid,r,a.F,a.S,ans.F,ans.S,sum[x[4]],nm[x[4]])
        // }
        if(sum[x[4]]>=ans.F){
            sum[x[4]]-=ans.F;
            nm[x[4]]-=ans.S;
            // if(x[4]==1){
            //     dbg(2,l,mid,r,a.F,a.S,ans.F,ans.S,sum[x[4]],nm[x[4]])
            // }

            ok.pb(x);
        }else nok.pb(x);
    }
    for(int i=l;i<=mid;i++){
        auto [c,a,b]=f[i];
        if(up[a][0]==b) swap(a,b);
        add(pos[b],-c);
    }
    if(l>=r) return;

    bs(l,mid,nok);
    bs(mid+1,r,ok);
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n>>m>>q;
for(int i=0;i+1<n;i++){
    int a,b;
    cin>>a>>b;
    v[a].pb(b);
    v[b].pb(a);
    mp3[i]={a,b};
    mp[{a,b}]=mp[{b,a}]=i;
}
for(int i=0;i<m;i++){
    int p,c;
    cin>>p>>c;
    p--;
    auto [a,b]=mp3[p];
    f.pb({c,a,b});
}
sort(all(f));
for(int i=0;i<q;i++){
    int s,t,x,y;
    cin>>s>>t>>x>>y;
    queries.pb({s,t,x,y,i});
    sum[i]=y;
}
dfs(1,1);
HLD(1,1,1);
for(int i=0;i<m;i++){
    auto [c,a,b]=f[i];
    if(up[a][0]==b) swap(a,b);
    add(pos[b],c);
    mp1[{a,b}]+=c;
    mp2[{a,b}]++;
}
for(auto x:queries){
    int l=LCA(x[0],x[1]);
    pii a = query(l,x[0]),b=query(l,x[1]);
    nm[x[4]]=a.S+b.S;
    // dbg(x[4],nm[x[4]])
}
for(int i=0;i<m;i++){
    auto [c,a,b]=f[i];
    if(up[a][0]==b) swap(a,b);
    add(pos[b],-c);
    mp1.erase({a,b});
    mp2.erase({a,b});
}
bs(0,m-1,queries);
for(auto x:queries){
    int a=x[0];
    int b=x[1];
    dbg(a,b,nm[x[4]],sum[x[4]],x[4])
    if(nm[x[4]]>x[2]) ans[x[4]]=-1;
    else ans[x[4]]=x[2]-nm[x[4]];
}
for(int i=0;i<q;i++){
    cout<<ans[i]<<endl;
}

}

Compilation message (stderr)

currencies.cpp: In function 'pii query(ll, ll)':
currencies.cpp:116:9: warning: unused variable 'vv' [-Wunused-variable]
  116 |     int vv=v;
      |         ^~
currencies.cpp: In function 'int main()':
currencies.cpp:17:18: warning: statement has no effect [-Wunused-value]
   17 | #define dbg(...) 1337;
      |                  ^~~~
currencies.cpp:238:5: note: in expansion of macro 'dbg'
  238 |     dbg(a,b,nm[x[4]],sum[x[4]],x[4])
      |     ^~~
currencies.cpp:236:9: warning: unused variable 'a' [-Wunused-variable]
  236 |     int a=x[0];
      |         ^
currencies.cpp:237:9: warning: unused variable 'b' [-Wunused-variable]
  237 |     int b=x[1];
      |         ^

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