Submission #727530

#	Time	Username	Problem	Language	Result	Execution time	Memory
727530		cig32	Two Currencies (JOI23_currencies)	C++17	100 / 100	3267 ms	173988 KiB

currencies

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int mxs = 1e14;
int32_t n, m, q;
vector<int> adj[MAXN];
int st[MAXN], en[MAXN], cur = 0;
bool is[MAXN];
int cost[MAXN];
pair<int,int> anc[19][2*MAXN];
int dep[MAXN];
vector<int> euler;
int dfn[2*MAXN];
void dfs(int node, int prv) {
  st[node] = ++cur;
  dfn[cur] = node;
  euler.push_back(node);
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  for(int x: adj[node]) {
    if(x != prv) {
      dfs(x, node);
      euler.push_back(node);
    }
  }
  en[node] = ++cur;
  dfn[cur] = node;
}
int ans[MAXN];
int block;
int32_t s[MAXN], t[MAXN], x[MAXN];
int y[MAXN], p[MAXN]; //lca
int mi[MAXN], ma[MAXN], ord[MAXN];
int l[MAXN], r[MAXN];
int lca(int u, int v) {
  int m1 = min(mi[u], mi[v]), m2 = max(ma[u], ma[v]);
  int k = 32 - __builtin_clz(m2-m1+1) - 1;
  return min(anc[k][m1], anc[k][m2 - (1<<k) + 1]).second;
}
bool cmp(int qa, int qb) {
  if(l[qa] / block != l[qb] / block) return l[qa] / block < l[qb] / block;
  return r[qa] < r[qb];
}
pair<int,int> chkpt[MAXN];
int freq[MAXN];
int pos[MAXN];
int val[MAXN];
int sumblock[MAXN];
int cnt[MAXN];
inline void ins(int x) {
  int pp = pos[x];
  val[pp] = cost[x];
  cnt[pp / block]++;
  sumblock[pp / block] += cost[x];
}
inline void del(int x) {
  int pp = pos[x];
  val[pp] = 0;
  cnt[pp / block]--;
  sumblock[pp / block] -= cost[x];
}
inline void add(int x) {
  x = dfn[x];
  if(!is[x]) return;
  freq[x]++;
  if(freq[x] == 2) del(x);
  else ins(x);
}
inline void sub(int x) {
  x = dfn[x];
  if(!is[x]) return;
  freq[x]--;
  if(freq[x] == 0) del(x);
  else ins(x);
}
pair<int,int> sto[MAXN];
vector<int> stuff[MAXN];
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long x, long long y) {
  long long u = uniform_int_distribution<long long>(x, y)(rng);
  return u;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  scanf("%d %d %d", &n, &m, &q);
  for(int i=0; i+1<n; i++) {
    int32_t u, v;
    scanf("%d %d", &u, &v);
    sto[i] = {u, v};
  }
  int rt = rnd(1, n);
  for(int i=0; i<m; i++) {
    int32_t p, c;
    scanf("%d %d", &p, &c);
    n++;
    p--;
    stuff[p].push_back(n);
    is[n] = 1;
    cost[n] = c;
    chkpt[i] = {c, n};
  }
  for(int i=0; i+1<n-m; i++) {
    int u = sto[i].first;
    int v = sto[i].second;
    if(stuff[i].empty()) {
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    else {
      adj[u].push_back(stuff[i][0]);
      adj[stuff[i][0]].push_back(u);
      for(int j=0; j+1<stuff[i].size(); j++) {
        adj[stuff[i][j]].push_back(stuff[i][j+1]);
        adj[stuff[i][j+1]].push_back(stuff[i][j]);
      }
      int fin = stuff[i].size() - 1;
      adj[stuff[i][fin]].push_back(v);
      adj[v].push_back(stuff[i][fin]);
    }
  }
  block = ceil(sqrt(n)) * 2;
  sort(chkpt, chkpt + m);
  for(int i=0; i<m; i++) pos[chkpt[i].second] = i;
  dfs(rt, -1);
  for(int i=0; i<euler.size(); i++) anc[0][i] = {dep[euler[i]], euler[i]};
  for(int i=0; i<euler.size(); i++) ma[euler[i]] = i;
  for(int i=euler.size()-1; i>=0; i--) mi[euler[i]] = i;
  for(int i=1; i<19; i++) {
    for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      anc[i][j] = min(anc[i-1][j], anc[i-1][j+(1<<(i-1))]);
    }
  }
  for(int i=1; i<=q; i++) {
    scanf("%d %d %d %lld", &s[i], &t[i], &x[i], &y[i]);
    if(st[s[i]] > st[t[i]]) swap(s[i], t[i]);
    p[i] = lca(s[i], t[i]);
    if(s[i] == p[i]) l[i] = st[s[i]], r[i] = st[t[i]];
    else l[i] = en[s[i]], r[i] = st[t[i]];
  }
  for(int i=1; i<=q; i++) ord[i] = i;
  sort(ord+1, ord+q+1, cmp);
  block = ceil(sqrt(m));
  int lprev = 0, rprev = 0;
  for(int i=1; i<=q; i++) {
    int idx = ord[i];
    int lnew = l[idx], rnew = r[idx];
    while(rprev < rnew) {
      rprev++; add(rprev);
    }
    while(lprev > lnew) {
      lprev--; add(lprev);
    }
    while(rprev > rnew) {
      sub(rprev); rprev--;
    }
    while(lprev < lnew) {
      sub(lprev); lprev++;
    }
    int run = 0; // number of checkpoints payable using silver
    int gold = x[idx], silver = y[idx];
    if(silver >= mxs) {
      ans[idx] = gold;
      continue;
    }
    int tcc = 0;
    bool pk = 0;
    for(int j=0; j<block; j++) {
      tcc += cnt[j];
      if(pk)continue;
      if(sumblock[j] <= silver) {
        silver -= sumblock[j];
        run += cnt[j];
      }
      else { 
        int mlm = min((int) m, (j+1) * block);
        for(int k=j*block; k<mlm; k++) {
          if(val[k] <= silver && val[k] > 0) {
            silver -= val[k];
            run++;
          }
        }
        pk = 1;
      }
    }
    gold -= (tcc - run);
    gold = max(gold, -1ll);
    ans[idx] = gold;
  }
  for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}
/*
4 6 1
1 2
2 3
1 4
2 1
4 1
3 5
3 2
4 2
3 2
1 4 2 6
*/

Compilation message (stderr)

currencies.cpp: In function 'int32_t main()':
currencies.cpp:115:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |       for(int j=0; j+1<stuff[i].size(); j++) {
      |                    ~~~^~~~~~~~~~~~~~~~
currencies.cpp:128:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for(int i=0; i<euler.size(); i++) anc[0][i] = {dep[euler[i]], euler[i]};
      |                ~^~~~~~~~~~~~~
currencies.cpp:129:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for(int i=0; i<euler.size(); i++) ma[euler[i]] = i;
      |                ~^~~~~~~~~~~~~
currencies.cpp:132:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~~~~~
currencies.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d %d %d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d %d", &p, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d %d %d %lld", &s[i], &t[i], &x[i], &y[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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