제출 #1174599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174599		JelalTkm	다리 (APIO19_bridges)	C++20	13 / 100	145 ms	2884 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1000 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

struct node {
  int u, v, w;
};

vector<multiset<pair<int, int>>> g(N, multiset<pair<int, int>> ());

int bfs(int start, int wj) {
  vector<bool> visited(g.size());
  queue<int> q;
  q.push(start);

  int ans = 0;

  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (!visited[v]) {
      ans++;
      for (auto i : g[v]) {;
        if (!visited[i.first] && i.second >= wj)
          q.push(i.first);
      }
      visited[v] = 1;
    }
  }

  return ans;
}

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    vector<node> a(m + 1);
    for (int i = 1; i <= m; i++) {
      cin >> a[i].u >> a[i].v >> a[i].w;
      g[a[i].u].insert({a[i].v, a[i].w});
      g[a[i].v].insert({a[i].u, a[i].w});
    }

    int q;
    cin >> q;
    while (q--) {
      int tp;
      cin >> tp;
      if (tp == 1) {
        int b, r;
        cin >> b >> r;
        g[a[b].u].erase(g[a[b].u].find({a[b].v, a[b].w}));
        g[a[b].v].erase(g[a[b].v].find({a[b].u, a[b].w}));
        g[a[b].u].insert({a[b].v, r});
        g[a[b].v].insert({a[b].u, r});
        a[b].w = r;
      } else {
        int s, w;
        cin >> s >> w;
        cout << bfs(s, w) << '\n';
      }
    }
  }

  return 0;
}

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