Submission #1095119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095119		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3074 ms	7352 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;
  };
};

std::vector<std::pair<int, int>> g[NMAX + 1];
bool vis[NMAX + 1];

void dfs(int u, int W) {
  vis[u] = true;
  for (const auto &[v, w] : g[u]) {
    if (!vis[v] && w >= W) {
      dfs(v, 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;

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

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

  int q;
  std::cin >> q;

  while (q--) {
    int type;
    std::cin >> type;
    if (type == 1) {
      int index, w;
      std::cin >> index >> w;
      e[index - 1].w = w;
      for (int i = 1; i <= n; i++) {
        g[i].clear();
      }
      for (const auto &[u, v, w] : e) {
        g[u].push_back({v, w});
        g[v].push_back({u, w});
      }
    } else {
      int u, w;
      std::cin >> u >> w;
      for (int i = 1; i <= n; i++) {
        vis[i] = false;
      }
      dfs(u, w);
      int answer = 0;
      for (int i = 1; i <= n; i++) {
        answer += vis[i];
      }
      std::cout << answer << '\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: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27