Submission #1367264

#TimeUsernameProblemLanguageResultExecution timeMemory
1367264vjudge1Bridges (APIO19_bridges)C++20
13 / 100
149 ms5304 KiB
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using l3 = array<ll, 3>;

// sub 1

int n, m, q, sz[1005], pa[1005];
vector<l3> edges;

int find(int x) {
  if (x == pa[x]) return x;
  return pa[x] = find(pa[x]);
}

void unite(int x, int y) {
  if ((x = find(x)) == (y = find(y))) return;
  if (sz[x] > sz[y]) swap(x, y);
  pa[x] = y;
  sz[y] += sz[x];
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    edges.push_back({w, u, v});
  }
  cin >> q;
  while (q--) {
    int a, b, c; cin >> a >> b >> c;
    if (a == 1) edges[b-1][0] = c;
    if (a == 2) {
      for (int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;
      auto e = edges;
      sort(e.begin(), e.end(), greater<>());
      for (auto [w, u, v]: e) {
        if (w < c) break;
        // cout << w << u << v << '\n';
        unite(u, v);
      }
      cout << sz[find(b)] << '\n';
    }
  }
};
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...