Submission #966693

#	Time	Username	Problem	Language	Result	Execution time	Memory
966693		kilkuwu	Bridges (APIO19_bridges)	C++17	13 / 100	3054 ms	7312 KiB

bridges

#include <bits/stdc++.h>

#define nl '\n'

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;

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

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

  auto solve = [&](int s, int w) {
    std::queue<int> q;
    std::vector<int> vis(n, 0);
    q.emplace(s);
    vis[s] = 1;
    int cnt = 0;
    while (q.size()) {
      int u = q.front();
      q.pop();
      cnt++;
      
      for (int eid : adj[u]) {
        int v = edges[eid].other(u);
        if (edges[eid].d < w) continue;
        if (!vis[v]) {
          vis[v] = 1;
          q.emplace(v);
        }
      }
    }
    return cnt;
  };

  int q;
  std::cin >> q;
  while (q--) {
    int t;
    std::cin >> t;
    if (t == 1) {
      int i, v;
      std::cin >> i >> v;
      --i;
      edges[i].d = v;
    } else {
      int s, w;
      std::cin >> s >> w;
      --s;
      std::cout << solve(s, w) << nl;
    }
  }
}

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