Submission #1174302

#TimeUsernameProblemLanguageResultExecution timeMemory
1174302domblyBridges (APIO19_bridges)C++20
13 / 100
3093 ms3636 KiB
#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"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...