oj.uz

Submission #969913

# Submission time Handle Problem Language Result Execution time Memory
969913 2024-04-25T19:38:06 Z mychecksedad Two Currencies (JOI23_currencies) C++17
30 / 100
 646 ms 270780 KB 
/* 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;
    if(val <= rsilver) return nm;
    return 0;
  }
  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){
    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; 
  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] + E[U.second].size();
      dfs(u, v);
      up[u][0] = v;
    }
  }
}
 
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){
      timer += E[U.second].size();
      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++]});
    }
  }
  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;
  dfs(1, 1);
  int tm = 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));
  int c = 0;
  for(int i = 0; i < mi*2; ++i) if(X[i].second > 0) pos[X[i].second] = ++c;
 
  roots.pb(build(1, mi));
  for(int i = 1; i <= mi*2; ++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 = 0; i < q; ++i){
    int s, t; ll x, y; cin >> s >> t >> x >> y;
    int lca = _lca(s, t);
    int tot_gold = sum[s] + sum[t] - 2*sum[lca];
    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));
    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

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:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |   int m = l+r>>1;
      |           ~^~
currencies.cpp: In function 'int main()':
currencies.cpp:190:15: warning: unused variable 'aa' [-Wunused-variable]
  190 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 121516 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 121572 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct
2 Correct 18 ms 62924 KB Output is correct
3 Correct 18 ms 63068 KB Output is correct
4 Correct 18 ms 63068 KB Output is correct
5 Correct 352 ms 201320 KB Output is correct
6 Correct 310 ms 175976 KB Output is correct
7 Correct 480 ms 245128 KB Output is correct
8 Correct 646 ms 270528 KB Output is correct
9 Correct 632 ms 270780 KB Output is correct
10 Correct 616 ms 270528 KB Output is correct
11 Correct 591 ms 270248 KB Output is correct
12 Correct 552 ms 269872 KB Output is correct
13 Correct 563 ms 269916 KB Output is correct
14 Correct 441 ms 270584 KB Output is correct
15 Correct 399 ms 270608 KB Output is correct
16 Correct 454 ms 270576 KB Output is correct
17 Correct 447 ms 270656 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 121516 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -