Submission #798340

#	Time	Username	Problem	Language	Result	Execution time	Memory
798340		huutuan	Two Currencies (JOI23_currencies)	C++14	100 / 100	1624 ms	62832 KiB

currencies

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

struct FenwickTree{
   int n; vector<int> t;

   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }

   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }

   void update(int l, int r, int val){
      update(l, val);
      update(r+1, -val);
   }

   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
} bit, bit2;

struct nigga{
   int s, t, x, y;
   nigga(int a=0, int b=0, int c=0, int d=0): s(a), t(b), x(c), y(d){};
};

const int N=1e5+1, LG=17;
int n, m, q, tdfs, tin[N], tout[N], up[N][LG], dep[N], l[N], r[N], ans[N];
vector<int> g[N], vv[N];
nigga a[N];

void dfs(int u){
   tin[u]=++tdfs;
   dep[u]=dep[up[u][0]]+1;
   for (int v:g[u]) if (v!=up[u][0]){
      up[v][0]=u;
      for (int k=1; k<LG; ++k) up[v][k]=up[up[v][k-1]][k-1];
      dfs(v);
   }
   tout[u]=tdfs;
}

int lca(int u, int v){
   if (dep[u]!=dep[v]){
      if (dep[u]<dep[v]) swap(u, v);
      int d=dep[u]-dep[v];
      for (int k=0; k<LG; ++k) if (d>>k&1) u=up[u][k];
   }
   if (u==v) return u;
   for (int k=LG-1; k>=0; --k) if (up[u][k]!=up[v][k]) u=up[u][k], v=up[v][k];
   return up[u][0];
}

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   cin >> n >> m >> q;
   vector<pair<int, int>> edges;
   for (int i=1; i<n; ++i){
      int x, y; cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
      edges.emplace_back(x, y);
   }
   dfs(1);
   vector<pair<int, int>> pts{{0, 0}};
   bit2.init(n);
   for (int i=1; i<=m; ++i){
      int p, c; cin >> p >> c; --p;
      int x=edges[p].first, y=edges[p].second;
      if (tin[x]>tin[y]) swap(x, y);
      pts.emplace_back(c, y);
      bit2.update(tin[y], tout[y], 1);
   }
   sort(all(pts));
   for (int i=1; i<=q; ++i){
      cin >> a[i].s >> a[i].t >> a[i].x >> a[i].y;
      l[i]=0, r[i]=sz(pts)-1;
   }
   for (int rep=0; rep<LG; ++rep){
      for (int i=1; i<=q; ++i) if (l[i]<=r[i]) vv[(l[i]+r[i])>>1].push_back(i);
      bit.init(n);
      for (int i=0; i<sz(pts); ++i){
         if (i) bit.update(tin[pts[i].second], tout[pts[i].second], pts[i].first);
         for (int j:vv[i]){
            int u=a[j].s, v=a[j].t, w=lca(u, v);
            int sum_silver=bit.get(tin[u])+bit.get(tin[v])-(bit.get(tin[w])<<1);
            if (sum_silver<=a[j].y) l[j]=i+1;
            else r[j]=i-1;
         }
         vv[i].clear();
      }
   }
   for (int i=1; i<=q; ++i) vv[r[i]].push_back(i);
   bit.init(n);
   for (int i=0; i<sz(pts); ++i){
      if (i) bit.update(tin[pts[i].second], tout[pts[i].second], 1);
      for (int j:vv[i]){
         int u=a[j].s, v=a[j].t, w=lca(u, v);
         int cnt_silver=bit.get(tin[u])+bit.get(tin[v])-(bit.get(tin[w])<<1);
         int cnt_pts=bit2.get(tin[u])+bit2.get(tin[v])-(bit2.get(tin[w])<<1);
         int cnt_gold=cnt_pts-cnt_silver;
         ans[j]=a[j].x-min(cnt_gold, a[j].x+1);
      }
      vv[i].clear();
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

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