Submission #1095102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095102		thangdz2k7	Two Currencies (JOI23_currencies)	C++17	100 / 100	468 ms	75720 KiB

currencies

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, q, l[N], r[N];
int a[N], b[N], s[N], t[N], x[N], lca[N];
ll y[N];
ii p[N];
vi adj[N], query[N];
int t_in[N], t_out[N], cnt = 0;

void dfs(int u = 1, int p = 0){
    t_in[u] = ++ cnt;
    for (int v : adj[u]) if (v ^ p) dfs(v, u);
    t_out[u] = cnt;
}

template <class T>
struct RMQ { // 0-based
  vector<vector<T>> rmq;
  T kInf = numeric_limits<T>::max();
  void build(const vector<T>& V) {
    int n = V.size(), on = 1, dep = 1;
    while (on < n) on *= 2, ++dep;
    rmq.assign(dep, V);

    for (int i = 0; i < dep - 1; ++i)
      for (int j = 0; j < n; ++j) {
        rmq[i + 1][j] = min(rmq[i][j], rmq[i][min(n - 1, j + (1 << i))]);
      }
  }
  T query(int a, int b) { // [a, b)
    if (b <= a) return kInf;
    int dep = 31 - __builtin_clz(b - a); // log(b - a)
    return min(rmq[dep][a], rmq[dep][b - (1 << dep)]);
  }
};

struct LCA { // 0-based
  vector<int> enter, depth, exxit;
  vector<vector<int>> G;
  vector<pair<int, int>> linear;
  RMQ<pair<int, int>> rmq;
  int timer = 0;
  LCA() {}
  LCA(int n) : enter(n, -1), exxit(n, -1), depth(n), G(n), linear(2 * n) {}
  void dfs(int node, int dep) {
    linear[timer] = {dep, node};
    enter[node] = timer++;
    depth[node] = dep;
    for (auto vec : G[node])
    if (enter[vec] == -1) {
      dfs(vec, dep + 1);
      linear[timer++] = {dep, node};
    }
    exxit[node] = timer;
  }
  void add_edge(int a, int b) {
    G[a].push_back(b);
    G[b].push_back(a);
  }
  void build(int root) {
    dfs(root, 0);
    rmq.build(linear);
  }
  int query(int a, int b) {
    a = enter[a], b = enter[b];
    return rmq.query(min(a, b), max(a, b) + 1).second;
  }
  int dist(int a, int b) {
    return depth[a] + depth[b] - 2 * depth[query(a, b)];
  }
};

pair <ll, int> ans[N], bit[N];

void update(int l, int r, int x){
    for (; l <= n; l += l & -l) bit[l].fi += x, bit[l].se ++;
    for (r = r + 1; r <= n; r += r & -r) bit[r].fi -= x, bit[r].se --;
}

pair <ll, int> gett(int k){
    pair <ll, int> ans = {0, 0};
    for (; k; k -= k & -k) ans.fi += bit[k].fi, ans.se += bit[k].se;
    return ans;
}

pair <ll, int> qry(int id){
    pair <ll, int> vs = gett(t_in[s[id]]);
    pair <ll, int> vt = gett(t_in[t[id]]);
    pair <ll, int> vlca = gett(t_in[lca[id]]);
    return pair <ll, int> (vs.fi + vt.fi - vlca.fi * 2, vs.se + vt.se - vlca.se * 2);
}

void process(){
    for (int i = 1; i <= n; ++ i) bit[i] = {0, 0};
    for (int id = 0; id <= m; ++ id){
        if (id){
            int i = p[id].se, u = b[i], w = p[id].fi;
            update(t_in[u], t_out[u], w);
        }
        for (int t : query[id]){
            pair <ll, int> cur = qry(t);
            if (cur.fi <= y[t]) ans[t] = cur, l[t] = id + 1;
            else r[t] = id - 1;
        }
    }
}

void solve(){
    cin >> n >> m >> q; LCA T(n + 1);
    for (int i = 1; i < n; ++ i){
        cin >> a[i] >> b[i];
        adj[a[i]].pb(b[i]); adj[b[i]].pb(a[i]);
        T.add_edge(a[i], b[i]);
    }

    dfs(); T.build(1);
    for (int i = 1; i < n; ++ i){
        if (t_in[a[i]] > t_in[b[i]]) swap(a[i], b[i]);
    }

    for (int i = 1; i <= m; ++ i){
        cin >> p[i].se >> p[i].fi;
    }
    sort(p + 1, p + m + 1);

    for (int i = 1; i <= q; ++ i){
        cin >> s[i] >> t[i] >> x[i] >> y[i];
        l[i] = 0, r[i] = m; lca[i] = T.query(s[i], t[i]);
    }

    while (true){
        bool ck = false;
        for (int i = 1; i <= q; ++ i){
            if (l[i] > r[i]) continue;
            int mid = l[i] + r[i] >> 1;
            query[mid].pb(i); ck = true;
        }
        if (!ck) {
            for (int i = 1; i <= q; ++ i){
                pair <ll, int> cur = qry(i);
                ans[i].se = cur.se - ans[i].se;
            }
            break;
        }
        process();
        for (int i = 1; i <= m; ++ i) query[i].clear();
    }

    for (int i = 1; i <= q; ++ i){
        if (ans[i].se <= x[i]) cout << x[i] - ans[i].se << endl;
        else cout << -1 << endl;
    }
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

/*
10 7 9
1 8
6 3
5 9
7 9
3 1
3 4
10 1
2 6
5 6
9 4
7 4
7 4
2 4
7 4
7 4
1 4
8 6 5 3
3 9 8 0
4 7 6 15
7 4 9 3
6 4 8 0
9 10 5 16
5 3 2 4
2 8 4 3
6 1 3 3
*/

Compilation message (stderr)

currencies.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
currencies.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
currencies.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
currencies.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
currencies.cpp: In constructor 'LCA::LCA(int)':
currencies.cpp:56:29: warning: 'LCA::exxit' will be initialized after [-Wreorder]
   56 |   vector<int> enter, depth, exxit;
      |                             ^~~~~
currencies.cpp:56:22: warning:   'std::vector<int> LCA::depth' [-Wreorder]
   56 |   vector<int> enter, depth, exxit;
      |                      ^~~~~
currencies.cpp:62:3: warning:   when initialized here [-Wreorder]
   62 |   LCA(int n) : enter(n, -1), exxit(n, -1), depth(n), G(n), linear(2 * n) {}
      |   ^~~
currencies.cpp: In function 'void solve()':
currencies.cpp:153:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |             int mid = l[i] + r[i] >> 1;
      |                       ~~~~~^~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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