Submission #1095088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095088		vjudge1	Bridges (APIO19_bridges)	C++17	0 / 100	49 ms	6484 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;
  };
};

int p[NMAX + 1];
int up[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, int w) {
  u = root(u);
  v = root(v);
  if (u != v) {
    if (sz[u] > sz[v]) {
      std::swap(u, v);
    }
    sz[v] += sz[u];
    p[u] = v;
    up[u] = w;
  }
}
int getSize(int u, int w) {
  return (p[u] == u || w > up[u])? sz[u] : getSize(p[u], w);
}

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;
    up[i] = 0;
    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());

  for (const auto &[u, v, w] : e) {
    join(u, v, w);
  }

  int q;
  std::cin >> q;
  while (q--) {
    int type;
    std::cin >> type;
    if (type == 1) {
      break;
    } else {
      int u, w;
      std::cin >> u >> w;
      std::cout << getSize(u, w) << '\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: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27