Submission #991137

#	Time	Username	Problem	Language	Result	Execution time	Memory
991137		ThMinh_	Two Currencies (JOI23_currencies)	C++17	100 / 100	676 ms	208840 KiB

currencies

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, m, q, it;
int road[N << 1], st[N], ed[N], h[N], par[18][N];
vector<int> adj[N];
vector<ll> vt, gin[N];
pair<int, int> e[N];

void init() {
   cin>>n>>m>>q;
   for(int i = 1; i <= n - 1; ++i) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
      e[i] = {u, v};
   }
}

void dfs(int u) {
   road[++it] = u;
   st[u] = it;
   for(auto v : adj[u]) if(v != par[0][u]) {
      h[v] = h[u] + 1;
      par[0][v] = u;
      for(int i = 1; i <= log2(n); ++i) par[i][v] = par[i - 1][par[i - 1][v]];
      dfs(v);
   }
   road[++it] = u;
   ed[u] = it;
}

int lca(int x, int y) {
   if(h[x] < h[y]) swap(x, y);
   int delta = h[x] - h[y];
   for(int i = 0; i <= log2(n); ++i) if((delta >> i) & 1) {
      x = par[i][x];
   }
   if(x == y) return x;
   for(int i = log2(n); i >= 0; --i) if(par[i][x] != par[i][y]) {
      x = par[i][x];
      y = par[i][y];
   }
   return par[0][x];
}

int child(int p, int x) {
   int delta = h[x] - h[p] - 1;
   if(delta == -1) return st[p];
   for(int i = 0; i <= log2(n); ++i) if((delta >> i) & 1) {
      x = par[i][x];
   }
   return st[x] - 1;
}

struct Tree {
   ll cnt, sum;
   Tree* lf;
   Tree* rt;
   Tree() : sum(), cnt(), lf(), rt() { }
};

ll sum(Tree* id) {
   return id ? id -> sum : 0;
}

ll cnt(Tree* id) {
   return id ? id -> cnt : 0;
}

void up(Tree* id, int f, int l, int i, ll val1, ll val2) {
   if(f == l) {
      id -> sum += val1;
      id -> cnt += val2;
      return;
   }
   int mid = f + l >> 1;
   if(i <= mid) {
      id -> lf = id -> lf ? new Tree(*id -> lf) : new Tree();
      up(id -> lf, f, mid, i, val1, val2);
   }
   else {
      id -> rt = id -> rt ? new Tree(*id -> rt) : new Tree();
      up(id -> rt, mid + 1, l, i, val1, val2);
   }
   id -> sum = sum(id -> lf) + sum(id -> rt);
   id -> cnt = cnt(id -> lf) + cnt(id -> rt);
}

ll get(Tree* fu, Tree* lu, Tree* fv, Tree* lv, int f, int l, ll val) {
   if(f == l) {
      ll dd = val / vt[f - 1];
      ll gold = cnt(lu) - cnt(fu) + cnt(lv) - cnt(fv);
      return max(0ll, gold - dd);
   }
   int mid = f + l >> 1;

   ll silver = sum(lu -> lf) - sum(fu -> lf) + sum(lv -> lf) - sum(fv -> lf);
   if(silver >= val) {
      if(!fu -> lf) fu -> lf = new Tree(); if(!lu -> lf) lu -> lf = new Tree();
      if(!fv -> lf) fv -> lf = new Tree(); if(!lv -> lf) lv -> lf = new Tree();
      ll gold = cnt(lu -> rt) - cnt(fu -> rt) + cnt(lv -> rt) - cnt(fv -> rt);
      return get(fu -> lf, lu -> lf, fv -> lf, lv -> lf, f, mid, val) + gold;
   }
   else {
      if(!fu -> rt) fu -> rt = new Tree(); if(!lu -> rt) lu -> rt = new Tree();
      if(!fv -> rt) fv -> rt = new Tree(); if(!lv -> rt) lv -> rt = new Tree();
      return get(fu -> rt, lu -> rt, fv -> rt, lv -> rt, mid + 1, l, val - silver);
   }
}

int32_t main () {
   cin.tie(0)->sync_with_stdio(0);
   if(fopen("Task.inp","r")) {
      freopen("Task.inp","r",stdin);
      freopen("WA.out","w",stdout);
   }

   init();

   dfs(1);
   while(m--) {
      int r; ll c; cin>>r>>c;
      int u, v; tie(u, v) = e[r];
      if(h[u] < h[v]) swap(u, v);
      gin[u].push_back(c);
      vt.push_back(c);
   }
   sort(vt.begin(), vt.end());
   vt.resize(unique(vt.begin(), vt.end()) - vt.begin());

   int mx = vt.size();
   vector<Tree*> tr;

   tr.resize(it + 1);
   tr[0] = new Tree();
   for(int i = 1; i <= it; ++i) {
      int u = road[i];
      tr[i] = new Tree(*tr[i - 1]);

      if(i == st[u]) for(auto c : gin[u]) {
         int pos = upper_bound(vt.begin(), vt.end(), c) - vt.begin();
         up(tr[i], 1, mx, pos, c, 1);
      }
      if(i == ed[u]) for(auto c : gin[u]) {
         int pos = upper_bound(vt.begin(), vt.end(), c) - vt.begin();
         up(tr[i], 1, mx, pos, -c, -1);
      }
   }

   while(q--) {
      int s, t, x; ll y; cin >> s >> t >> x >> y;
      if(st[s] > st[t]) swap(s, t);
      int p = lca(s, t);
      int u = child(p, s);
      int v = child(p, t);

      ll ans = get(tr[u], tr[st[s]], tr[v], tr[st[t]], 1, mx, y);
      if(ans > x) cout << "-1\n";
      else cout << x - ans << "\n";
   }
}

Compilation message (stderr)

currencies.cpp: In constructor 'Tree::Tree()':
currencies.cpp:58:12: warning: 'Tree::sum' will be initialized after [-Wreorder]
   58 |    ll cnt, sum;
      |            ^~~
currencies.cpp:58:7: warning:   'long long int Tree::cnt' [-Wreorder]
   58 |    ll cnt, sum;
      |       ^~~
currencies.cpp:61:4: warning:   when initialized here [-Wreorder]
   61 |    Tree() : sum(), cnt(), lf(), rt() { }
      |    ^~~~
currencies.cpp: In function 'void up(Tree*, int, int, int, long long int, long long int)':
currencies.cpp:78:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |    int mid = f + l >> 1;
      |              ~~^~~
currencies.cpp: In function 'long long int get(Tree*, Tree*, Tree*, Tree*, int, int, long long int)':
currencies.cpp:97:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |    int mid = f + l >> 1;
      |              ~~^~~
currencies.cpp:101:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  101 |       if(!fu -> lf) fu -> lf = new Tree(); if(!lu -> lf) lu -> lf = new Tree();
      |       ^~
currencies.cpp:101:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  101 |       if(!fu -> lf) fu -> lf = new Tree(); if(!lu -> lf) lu -> lf = new Tree();
      |                                            ^~
currencies.cpp:102:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  102 |       if(!fv -> lf) fv -> lf = new Tree(); if(!lv -> lf) lv -> lf = new Tree();
      |       ^~
currencies.cpp:102:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  102 |       if(!fv -> lf) fv -> lf = new Tree(); if(!lv -> lf) lv -> lf = new Tree();
      |                                            ^~
currencies.cpp:107:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  107 |       if(!fu -> rt) fu -> rt = new Tree(); if(!lu -> rt) lu -> rt = new Tree();
      |       ^~
currencies.cpp:107:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  107 |       if(!fu -> rt) fu -> rt = new Tree(); if(!lu -> rt) lu -> rt = new Tree();
      |                                            ^~
currencies.cpp:108:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  108 |       if(!fv -> rt) fv -> rt = new Tree(); if(!lv -> rt) lv -> rt = new Tree();
      |       ^~
currencies.cpp:108:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  108 |       if(!fv -> rt) fv -> rt = new Tree(); if(!lv -> rt) lv -> rt = new Tree();
      |                                            ^~
currencies.cpp: In function 'int32_t main()':
currencies.cpp:116:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |       freopen("Task.inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:117:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |       freopen("WA.out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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