Submission #1174302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174302		dombly	Bridges (APIO19_bridges)	C++20	13 / 100	3093 ms	3636 KiB

bridges

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second

using namespace std;

const int N = 5e4 + 10;

const int inf = 1e9;

struct DSU {
  int par[N], siz[N];
  void Init(int n) {
    for(int i = 1; i <= n; i++) {
      par[i] = i;
      siz[i] = 1;
    }
  }
  int get(int x) {
    return (x == par[x] ? x : get(par[x]));
  }
  void unite(int u, int v) {
    u = get(u); v = get(v);
    if(u == v) return;
    if(siz[u] > siz[v]) swap(u, v);
    par[u] = v;
    siz[v] += siz[u];
  }
  int query(int u) {
    return siz[get(u)];
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m;
  cin >> n >> m;
  vector<array<int,3>> e(m + 1);
  for(int i = 1; i <= m; i++) {
    cin >> e[i][0] >> e[i][1] >> e[i][2];
  }
  int q;
  cin >> q;
  while(q--) {
    int type, i, v;
    cin >> type >> i >> v;
    if(type == 1) {
      e[i][2] = v;
    } else {
      DSU dsu;
      dsu.Init(n);
      for(int i = 1; i <= m; i++) if(e[i][2] >= v) dsu.unite(e[i][0], e[i][1]);
      cout << dsu.query(i) << "\n";
    }
  }
}

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