Submission #966752

#	Time	Username	Problem	Language	Result	Execution time	Memory
966752		kilkuwu	Bridges (APIO19_bridges)	C++17	16 / 100	74 ms	13392 KiB

bridges

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

struct DSU {
  std::vector<int> e;

  DSU(int n) : e(n, -1) {}

  int find(int u) {
    return e[u] < 0 ? u : e[u] = find(e[u]);
  }
  
  bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    if (e[u] > e[v]) std::swap(u, v);
    e[u] += e[v];
    e[v] = u;
    return true;
  } 

  bool same(int u, int v) {
    return find(u) == find(v);
  }
  
  int size(int u) {
    return -e[find(u)];
  }
};

template <typename T>
using PQG = std::priority_queue<T, std::vector<T>, std::greater<T>>;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n, m;
  std::cin >> n >> m;
  
  std::vector<std::vector<int>> adj(n);
  struct Edge {
    int u, v, d, i;

    inline int other(int x) { return u ^ v ^ x; }

    bool operator<(const Edge& rhs) {
      return d < rhs.d;
    }
  };

  std::vector<Edge> edges(m);
  for (int i = 0; i < m; i++) {
    int u, v, d;
    std::cin >> u >> v >> d;
    --u, --v;
    adj[u].emplace_back(i);
    adj[v].emplace_back(i);
    edges[i] = {u, v, d, i};
  }

  if (n == 1) {
    int q;
    std::cin >> q;
    while (q--) {
      int t, a, b;
      std::cin >> t >> a >> b;
      if (t == 2) {
        std::cout << 1 << nl;
      }
    }
    return 0;
  }

  int bsize = std::sqrt(n) + 1;
  int bcnt = ((n - 2) / bsize) + 1;
  std::vector<PQG<std::pair<int, int>>> maxv(bcnt);

  for (int i = 0; i < m; i++) {
    int b = i / bsize;
    maxv[b].push({edges[i].d, i});
  }

  auto count_left = [&](int u, int w) -> int {
    int b = (u - 1) / bsize;
    int lb = b * bsize;
    int ans = 0;
    for (int i = u - 1; i >= lb; i--) {
      if (edges[i].d < w) return ans;
      ans++;
    }

    // done all of it now 
    int bb = b - 1;
    for (; bb >= 0; bb--) {
      if (maxv[bb].top().first < w) {
        break;
      }
      ans += bsize;
    }

    if (bb >= 0) {
      for (int j = (bb + 1) * bsize - 1; j >= bb * bsize; j--) {
        if (edges[j].d < w) return ans;
        ans++;
      }
    }
    dbg(u, w, ans);
    return ans;
  };

  auto count_right = [&](int u, int w) -> int {
    if (u == n - 1) return 0;
    int b = u / bsize;
    int rb = std::min((b + 1) * bsize, m);
    dbg(u, rb);
    int ans = 0;
    for (int i = u; i < rb; i++) {
      if (edges[i].d < w) return ans;
      ans++;
    }

    // done all of it now 
    int bb = b + 1;
    for (; bb < bcnt; bb++) {
      dbg(bb, maxv[bb]);
      if (maxv[bb].top().first < w) {
        break;
      }
      int xx = bsize * bb;
      int yy = std::min((bb + 1) * bsize, m);
      dbg(xx, yy);
      ans += yy - xx;
    }
    dbg(bb, bcnt);

    if (bb < bcnt) {
      int rightb = std::min(m, (bb + 1) * bsize);
      for (int j = bb * bsize; j < rightb; j++) {
        if (edges[j].d < w) return ans;
        ans++;
      }
    }
    dbg(u, w, ans);
    return ans;
  };

  int q;
  std::cin >> q;
  while (q--) {
    int t, a, b;
    std::cin >> t >> a >> b;
    --a;
    if (t == 1) {
      int id = a / bsize;
      edges[a].d = b;
      maxv[id].push({edges[a].d, a});
      while (maxv[id].size()) {
        auto [x, y] = maxv[id].top();
        if (edges[y].d != x) {
          maxv[id].pop();
        } else {
          break;
        }
      }
      dbg(id, maxv[id].top(), maxv[id]);
    } else {
      std::cout << count_left(a, b) + count_right(a, b) + 1 << nl;
    }
  }
}

• Subtask 1: 0 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27