Submission #969911

#	Time	Username	Problem	Language	Result	Execution time	Memory
969911		mychecksedad	Two Currencies (JOI23_currencies)	C++17	100 / 100	794 ms	303312 KiB

currencies

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 20, MX = 30;
 
 
struct Node{
  Node *L, *R;
  ll sum;
  int num;
  Node(){
    L = R = nullptr;
    sum = num = 0;
  }
  Node(ll x, int nm){
    L = R = nullptr;
    sum = x;
    num = nm;
  }
  Node(Node *l, Node *r){
    L = l, R = r;
    sum = L->sum + R->sum;
    num = L->num + R->num;
  }
  void extend(){
    if(L == nullptr) L = new Node();
    if(R == nullptr) R = new Node();
  }
};
 
int n, mi, q, s[N], tin[N], tout[N], up[N][K], heavy[N], dep[N], par[N], ESZ[N], ttin[N], toutt[N], timerr = 0;
ll sum[N];
vector<pair<int, int>> g[N], euler;
vector<int> E[N];
vector<Node*> roots;
 
Node* build(int l, int r){
  if(l == r){
    return new Node();
  }
  int m = l+r>>1;
  return new Node(build(l, m), build(m+1, r));
}
 
Node *update(Node *v, int l, int r, int p, ll val){
  if(l == r){
    return new Node(val, val == 0 ? 0 : 1);
  }
  int m = l+r>>1;
  if(p <= m){
    return new Node(update(v->L, l, m, p, val), v->R);
  }
  return new Node(v->L, update(v->R, m+1, r, p, val));
}
 
int f(int l, int r, Node *u, Node *v, Node *uu, Node *vv, ll rsilver){
  
  if(l == r){
    ll val = v->sum - u->sum + vv->sum - uu->sum;
    int nm = v->num - u->num + vv->num - uu->num;
    // for(auto &pt: TV){
    //   val += pt.second->sum - pt.first->sum;
    //   nm += pt.second->num - pt.first->num;
    // }
    if(val <= rsilver) return nm;
    return 0;
  }
  // cout << v->L->sum - u->L->sum + vv->L->sum - uu->L->sum << ' ' << l  << ' ' << r << '|';
  // cout << v->L->num - u->L->num + vv->L->num - uu->L->num << ' ' << l  << ' ' << r << '\n';
  
  int m = l+r>>1;
  ll val = v->L->sum - u->L->sum + vv->L->sum - uu->L->sum;
  int nm = v->L->num - u->L->num + vv->L->num - uu->L->num;
  if(val <= rsilver){
    // for(auto &pt: TV) pt.first = pt.first->R, pt.second = pt.second->R;
    v = v->R;
    vv = vv->R;
    u = u->R;
    uu = uu->R;
    return nm + f(m+1, r, u, v, uu, vv, rsilver - val);
  }
  v = v->L;
  vv = vv->L;
  u = u->L;
  uu = uu->L; 
  // for(auto &pt: TV) pt.first = pt.first->L, pt.second = pt.second->L;
  return f(l, m, u, v, uu, vv, rsilver);
}
 
 
 
void dfs(int v, int p){
  s[v] = 1;
  par[v] = p;
  dep[v] = dep[p] + 1;
  for(auto &U: g[v]){
    int u = U.first;
    if(u != p){
      sum[u] = sum[v];
      for(auto x: E[U.second]) sum[u]++;
      dfs(u, v);
      up[u][0] = v;
      s[v] += s[u];
      if(s[u] > s[g[v][0].first] || g[v][0].first == p) swap(U, g[v][0]);
    }
  }
}
 
void dfs2(int v, int p, int &timer){
  // tin[v] = timer - 1;
  ttin[v] = timerr++;
  // euler.
  tin[v] = euler.size() + 1;
  for(auto &U: g[v]){
    int u = U.first;
    if(u != p){
      if(u == g[v][0].first) heavy[u] = heavy[v];
      else heavy[u] = u;
      timer += E[U.second].size();
      ESZ[u] = E[U.second].size();
      // tin[u] = euler.size() + 1;
      vector<int> V;
      for(auto x: E[U.second]){
        euler.pb({x, euler.size() + 1});
        V.pb(euler.size());
      }
      dfs2(u, v, timer);
      int c = 0;
      for(auto x: E[U.second]) euler.pb({x, -V[c++]});
      // tout[u] = euler.size();
    }
  }
  tout[v] = timer - 1;
  toutt[v] = timerr++;
}
 
bool is_parent(int u, int v){
  return ttin[u] <= ttin[v] && toutt[v] <= toutt[u];
}
 
int _lca(int u, int v){
  if(is_parent(u, v)) return u;
  if(is_parent(v, u)) return v;
  for(int j = K-1; j >= 0 ; --j){
    if(!is_parent(up[u][j], v)) u = up[u][j];
  }
  return up[u][0];
}
 
void solve(){
  cin >> n >> mi >> q;
  for(int i = 0; i < n - 1; ++i){
    int u, v; cin >> u >> v;
    g[u].pb({v, i+1});
    g[v].pb({u, i+1});
  }
  for(int i = 0; i < mi; ++i){
    int p, c; cin >> p >> c;
    E[p].pb(c);
  }
  dep[1] = 1;
  tin[1] = 1;
  sum[1] = 0;
  tout[1] = euler.size();
  dfs(1, 1);
  int tm = 1;
  heavy[1] = 1;
  dfs2(1, 1, tm);
  

  up[1][0] = 1;
  for(int j = 1; j < K; ++j) for(int i = 1; i <= n; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
 
  vector<pair<int, int>> X = euler;
  mi *= 2;
  vector<int> pos(mi+1);
  sort(all(X));
  for(int i = 0; i < mi; ++i) pos[abs(X[i].second)] = i + 1;
 
  roots.pb(build(1, mi));
  for(int i = 1; i <= mi; ++i){
    if(euler[i - 1].second > 0)
      roots.pb(update(roots.back(), 1, mi, pos[i], euler[i - 1].first));
    else
      roots.pb(update(roots.back(), 1, mi, pos[-euler[i - 1].second], 0));
  }
//   for(int i = 1; i <= mi; ++i){
//     cout << euler[i-1].first << ' ' << euler[i-1].second << '\n';
//   }
//   en;
//   en;
//   for(int i = 1; i <= n; ++i) cout << tin[i] << ' ';
//   en;
// en;
  // cout << roots[5]->sum - roots[2]->sum << ' ';
 
  // for(auto x: X){
  //   cout << x.first << ' ' << x.second << '\n';
  // }
  // for(int i = 1; i <= n; ++i) cout << tin[i] << ' ' << tout[i] << '\n';



  for(int i = 0; i < q; ++i){
    int s, t; ll x, y; cin >> s >> t >> x >> y;
    int lca = _lca(s, t);
    // vector<pair<int, int>> T;
    // if(lca != s){
    //   int v = s;
    //   while(v != lca){
    //     int next;
    //     if(dep[heavy[v]] <= dep[lca]){
    //       next = lca;
    //       if(tin[next] + 1 <= tin[v])
    //         T.pb({tin[next] + 1, tin[v]});
    //       break;
    //     }
    //     else{ 
    //       next = heavy[v];
    //       int L = tin[heavy[v]] - ESZ[heavy[v]] + 1;
    //       if(L <= tin[v])
    //         T.pb({L, tin[v]});
    //     }
    //     v = par[next];
    //   }
    // }
    // if(lca != t){
    //   int v = t;
    //   while(v != lca){
    //     int next;
    //     if(dep[heavy[v]] <= dep[lca]){
    //       next = lca;
    //       if(tin[next] + 1 <= tin[v])
    //         T.pb({tin[next] + 1, tin[v]});
    //       break;
    //     }
    //     else{ 
    //       next = heavy[v];
    //       int L = tin[heavy[v]] - ESZ[heavy[v]] + 1;
    //       if(L <= tin[v])
    //         T.pb({L, tin[v]});
    //     }
    //     v = par[next];
    //   }
    // }
    // cout << "q:";
 
    // cout << s << ' ' << t << ' ' << lca << '\n';
    // for(auto x:T) cout << x.first << ' ' << x.second << '\n';
 
    // en;en;
    int tot_gold = sum[s] + sum[t] - 2*sum[lca];
    // cout << tot_gold << ' ';
    // vector<pair<Node*, Node*>> TV;
    // for(auto x: T){
    //   TV.pb({roots[x.first - 1], roots[x.second]});
    //   tot_gold += x.second - x.first + 1; 
    // }
    // if(tin[s] > tin[t]) swap(s, t);
    // cout << s << ' ' << t << ' ' << tin[s] - 1 << ' ' << tout[t] << '\n';
    int rgold = x - (tot_gold - f(1, mi, roots[tin[lca] - 1], roots[tin[s] - 1], roots[tin[lca] - 1], roots[tin[t] - 1], y));
    // cout << f(1, mi, roots[tin[lca] - 1], roots[tin[s] - 1], roots[tin[lca] - 1], roots[tin[t] - 1], y) << "f";
    if(rgold < 0) cout << -1 << '\n';
    else cout << rgold << '\n';
  }
}
 
 
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

currencies.cpp: In function 'Node* build(int, int)':
currencies.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int m = l+r>>1;
      |           ~^~
currencies.cpp: In function 'Node* update(Node*, int, int, int, long long int)':
currencies.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int m = l+r>>1;
      |           ~^~
currencies.cpp: In function 'int f(int, int, Node*, Node*, Node*, Node*, long long int)':
currencies.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int m = l+r>>1;
      |           ~^~
currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:106:16: warning: unused variable 'x' [-Wunused-variable]
  106 |       for(auto x: E[U.second]) sum[u]++;
      |                ^
currencies.cpp: In function 'int main()':
currencies.cpp:278:15: warning: unused variable 'aa' [-Wunused-variable]
  278 |   int tt = 1, aa;
      |               ^~

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