Submission #954805

#	Time	Username	Problem	Language	Result	Execution time	Memory
954805		lto5	Two Currencies (JOI23_currencies)	C++17	100 / 100	595 ms	48940 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

namespace std {
#ifndef LOCAL
#define cerr \
  if (0) cerr
#endif
}  // namespace std

template <class T>
struct FT {
  vector<T> ft;
  FT(int _n = 0) {
    ft.assign(_n + 5, 0);
  }
  void upd(int id, T val) {
    for (; id < (int)ft.size(); id += id & -id) ft[id] += val;
  }
  T get(int id) {
    T ans = 0;
    for (; id > 0; id -= id & -id) ans += ft[id];
    return ans;
  }
};

const int N = 1e5 + 5;

int n, m, q;
pair<int, int> e[N];
vector<int> g[N];
int lc[N];
pair<int, int> mark[N];
array<int64_t, 4> qr[N];

int f[N][20];
int h[N];
int tin[N];
int tout[N];
int time_dfs;

int ans[N];
int lo[N], hi[N];
vector<int> rem[N];

void dfs(int u) {
  tin[u] = ++time_dfs;
  for (int i = 0; f[f[u][i]][i]; i++) {
    f[u][i + 1] = f[f[u][i]][i];
  }
  for (int v : g[u]) {
    if (v == f[u][0]) {
      continue;
    }
    f[v][0] = u;
    h[v] = h[u] + 1;
    dfs(v);
  }
  tout[u] = time_dfs;
}

void init() {
  h[1] = 1;
  dfs(1);
}

int lca(int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  while (h[u] > h[v]) {
    u = f[u][__lg(h[u] - h[v])];
  }
  if (u == v) {
    return u;
  }
  for (int i = __lg(h[u]); i >= 0; i--) {
    if (f[u][i] != f[v][i]) {
      u = f[u][i];
      v = f[v][i];
    }
  }
  return f[u][0];
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task "a"
#else
#define task ""
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    auto& [u, v] = e[i];
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  for (int i = 1; i <= m; i++) {
    cin >> mark[i].second >> mark[i].first;
  }
  init();
  for (int i = 1; i < n; i++) {
    auto& [u, v] = e[i];
    if (h[u] > h[v]) swap(u, v);
  }
  sort(mark + 1, mark + 1 + m, greater<pair<int, int>>());
  for (int i = 1; i <= q; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> qr[i][j];
    }
    lc[i] = lca(qr[i][0], qr[i][1]);
    lo[i] = 0, hi[i] = m;
    ans[i] = qr[i][2] + 1;
  }
  while (true) {
    for (int i = 0; i <= m; i++) {
      rem[i].clear();
    }
    int sus = 0;
    for (int i = 1; i <= q; i++) {
      if (lo[i] <= hi[i]) {
        sus = 1;
        rem[(lo[i] + hi[i]) >> 1].push_back(i);
      }
    }
    if (!sus) break;
    FT<int64_t> ft_sum(n);
    FT<int> ft_cnt(n);
    for (int i = 1; i <= m; i++) {
      auto [w, id] = mark[i];
      auto [u, v] = e[id];
      ft_sum.upd(tin[v], w);
      ft_sum.upd(tout[v] + 1, -w);
    }
    // used i largest marked edges
    for (int i = 0; i <= m; i++) {
      if (i) {
        auto [w, id] = mark[i];
        auto [u, v] = e[id];
        ft_sum.upd(tin[v], -w);
        ft_sum.upd(tout[v] + 1, +w);
        ft_cnt.upd(tin[v], 1);
        ft_cnt.upd(tout[v] + 1, -1);
      }
      for (int que : rem[i]) {
        int u = qr[que][0];
        int v = qr[que][1];
        int lca = lc[que];
        int64_t used_silver = ft_sum.get(tin[u]) + ft_sum.get(tin[v]) - 2 * ft_sum.get(tin[lca]);
        int used_gold = ft_cnt.get(tin[u]) + ft_cnt.get(tin[v]) - 2 * ft_cnt.get(tin[lca]);
        if (used_silver <= qr[que][3]) {
          ans[que] = used_gold;
          hi[que] = i - 1;
        } else {
          lo[que] = i + 1;
        }
      }
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << max<int64_t>(-1, qr[i][2] - ans[i]) << "\n";
  }
  return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int32_t main()':
currencies.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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