Submission #966725

#	Time	Username	Problem	Language	Result	Execution time	Memory
966725		kilkuwu	Bridges (APIO19_bridges)	C++17	14 / 100	108 ms	12996 KiB

bridges

#include <bits/stdc++.h>

#define nl '\n'

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)];
  }
};

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;
    }
  };
  // build a centroid or sth

  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};
  }

  auto e = edges;

  std::sort(e.rbegin(), e.rend());

  DSU dsu(n);


  int q;
  std::cin >> q;
  std::vector<std::array<int, 3>> queries;
  std::vector<int> ans(q, -1);

  for (int i = 0; i < q; i++) {
    int t, a, b;
    std::cin >> t >> a >> b;
    --a;
    if (t == 2) {
      queries.push_back({b, a, i});
    }
  }

  std::sort(queries.rbegin(), queries.rend());

  int j = 0;

  for (int i = 0; i < (int) queries.size(); i++) {
    while (j < m && e[j].d >= queries[i].at(0)) {
      auto [u, v, d, id] = e[j];
      dsu.merge(u, v);
      j++;
    }
    ans[queries[i].at(2)] = dsu.size(queries[i].at(1));
  }

  for (int i = 0; i < q; i++) {
    if (ans[i] != -1) std::cout << ans[i] << nl;
  }
}

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