Submission #1324471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324471		animal_migration	Two Currencies (JOI23_currencies)	C++17	100 / 100	584 ms	91104 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define eb emplace_back
#define rep(x,y,z) for (int x=y;x<z;x++)

//bld pseg, range sum, point add, bs on four trees 
const int mn=2e6;//1e5*4 + 1e5*17
vector<int> dis;
int sum[mn], num[mn], ll[mn], rr[mn];
int idx=0, rid=0;

#define m ((l+r)>>1)

int bld(int l, int r){
  int id=idx++;
  if (l==r){
    sum[id]=0;
    num[id]=0;
    return id;
  }
  ll[id]=bld(l,m);
  rr[id]=bld(m+1,r);
  sum[id]=0;
  num[id]=0;
  return id;
}

int upd(int od, int l, int r, vector<int> pos){
  if (pos.size()==0) return od;
  int id=idx++;
  if (l==r){
    sum[id]=sum[od]+dis[l]*pos.size();
    num[id]=num[od]+pos.size();
    return id;
  }
  int cl=0;
  for (int &i:pos) if (i<=m) cl++;
  vector<int> lpos(cl),rpos(pos.size()-cl);
  int cr=0; cl=0;
  for (int &i:pos) if (i<=m) lpos[cl++]=i; else rpos[cr++]=i;
  ll[id]=upd(ll[od],l,m,lpos);
  rr[id]=upd(rr[od],m+1,r,rpos);
  sum[id]=sum[ll[id]]+sum[rr[id]];
  num[id]=num[ll[id]]+num[rr[id]];
  return id;
}

int bs(int od, int id1, int id2, int rem, int cn, int l, int r){
  int nn=num[id1]+num[id2]-num[od]*2;
  if (l==r) return cn+min(rem/dis[l],nn);
  int vl=sum[ll[id1]]+sum[ll[id2]]-sum[ll[od]]*2;
  int nl=num[ll[id1]]+num[ll[id2]]-num[ll[od]]*2;
  if (rem>=vl) return bs(rr[od],rr[id1],rr[id2],rem-vl,cn+nl,m+1,r);
  return bs(ll[od],ll[id1],ll[id2],rem,cn,l,m);
}

#undef m

signed main(){
  cin.tie(nullptr)->ios::sync_with_stdio(0);
  int n,m,q;
  cin>>n>>m>>q;
  vector<vector<int>> adj(n);
  vector<pii> edg(n-1);
  rep(i,0,n-1){
    int ca,cb;
    cin>>ca>>cb;
    ca--; cb--;
    adj[ca].pb(cb);
    adj[cb].pb(ca);
    edg[i]={ca,cb};
  }
  vector<int> dep(n), lf(n), ff(n);
  function<void(int,int)> cal=[&](int u, int f){
    ff[u]=f;
    int p=lf[ff[u]], q=lf[p];
    if (dep[ff[u]]-dep[p]==dep[p]-dep[q]&&u!=f) lf[u]=q;
    else lf[u]=ff[u];
    for (int v:adj[u]){
      if (v==f) continue;
      dep[v]=dep[u]+1;
      cal(v,u);
    }
  };
  dep[0]=0;
  cal(0,0);
  dis.resize(m);
  vector<vector<int>> add(n);
  rep(i,0,m){
    int x,v;
    cin>>x>>v;
    x--;
    int ca,cb;
    tie(ca,cb)=edg[x];
    if (dep[ca]<dep[cb]) swap(ca,cb);
    add[ca].pb(v);
    dis[i]=v;
  }
  sort(all(dis));
  dis.resize(unique(all(dis))-dis.begin());
  rep(i,0,n){
    for (int &j:add[i]){
      j=lower_bound(all(dis),j)-dis.begin();
    }
  }
  int k=dis.size();
  vector<int> frt(n);
  vector<int> rt(n);
  vector<int> cnt(n);
  frt[0]=bld(0,k-1);
  function<void(int,int)> dfs=[&](int u, int f){
    cnt[u]=cnt[f]+add[u].size();
    rt[u]=upd(frt[u],0,k-1,add[u]);
    for (int v:adj[u]){
      if (v==f) continue;
      frt[v]=rt[u];
      dfs(v,u);
    }
  };
  dfs(0,0);
  while (q--){
    int s,t,x,y;
    cin>>s>>t>>x>>y;
    s--; t--;
    int ls=s, lt=t;
    while (dep[ls]>dep[lt]){
      if (dep[lf[ls]]>=dep[lt]) ls=lf[ls];
      else ls=ff[ls];
    }
    while (dep[lt]>dep[ls]){
      if (dep[lf[lt]]>=dep[ls]) lt=lf[lt];
      else lt=ff[lt];
    }
    while (ls!=lt){
      if (lf[ls]!=lf[lt]) ls=lf[ls],lt=lf[lt];
      else ls=ff[ls], lt=ff[lt];
    }
    int lca=ls;
    //int bs(int od, int id1, int id2, int rem, int cn, int l, int r){
    int res=bs(rt[lca],rt[s],rt[t],y,0,0,k-1);
    int tot=cnt[s]+cnt[t]-cnt[lca]*2;
    // cout<<s+1<<' '<<t+1<<' '<<lca+1<<'\n';
    // cout<<tot<<' '<<res<<'\n';
    if ((tot-res)<=x) cout<<x-(tot-res)<<'\n';
    else cout<<"-1\n";
  }
  return 0;
}

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