Submission #1095115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095115		vjudge1	Bridges (APIO19_bridges)	C++17	14 / 100	55 ms	8532 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int INF = 1e9;
const int NMAX = 5e4;

struct Edge {
  int u, v, w;
  bool operator < (const Edge &other) const {
    return w > other.w;
  };
};

struct Query {
  int index, u, w;
  bool operator < (const Query &other) const {
    return w > other.w;
  };
};

int p[NMAX + 1];
int sz[NMAX + 1];

int root(int u) {
  return p[u] == u? u : p[u] = root(p[u]);
}
void join(int u, int v) {
  u = root(u);
  v = root(v);
  if (u != v) {
    if (sz[u] > sz[v]) {
      std::swap(u, v);
    }
    p[u] = v;
    sz[v] += sz[u];
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n, m;
  std::cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    p[i] = i;
    sz[i] = 1;
  }

  std::vector<Edge> e(m);

  for (auto &[u, v, w] : e) {
    std::cin >> u >> v >> w;
  }

  std::sort(e.begin(), e.end());

  int q;
  std::cin >> q;

  std::vector<Query> Q(q);
  for (int i = 0; i < q; i++) {
    int type;
    std::cin >> type;
    Q[i].index = i;
    std::cin >> Q[i].u >> Q[i].w;
  }

  std::sort(Q.begin(), Q.end());

  std::vector<int> answer(q, 0);

  e.push_back({-1, -1, 0});

  for (int i = 0, j = 0; i <= m && j < q;) {
    if (e[i].w >= Q[j].w) {
      join(e[i].u, e[i].v);
      i++;
    } else {
      answer[Q[j].index] = sz[root(Q[j].u)];
      j++;
    }
  }

  for (int i = 0; i < q; i++) {
    std::cout << answer[i] << '\n';
  }

  return 0;
}

Compilation message (stderr)

bridges.cpp:5:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    5 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

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