Submission #926320

#TimeUsernameProblemLanguageResultExecution timeMemory
926320TAhmed33Bridges (APIO19_bridges)C++98
13 / 100
3033 ms4348 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e4 + 25; int n, m; struct DSU { int sze[MAXN], par[MAXN]; void init (int n) { for (int i = 1; i <= n; i++) { sze[i] = 1; par[i] = i; } } int find (int x) { return par[x] == x ? x : par[x] = find(par[x]); } void merge (int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sze[a] > sze[b]) swap(a, b); sze[b] += sze[a]; par[a] = b; } } cur; array <int, 3> p[MAXN]; int main () { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; p[i] = {a, b, c}; } int q; cin >> q; while (q--) { int t; cin >> t; if (t == 1) { int a, b; cin >> a >> b; p[a][2] = b; } else { int x, y; cin >> x >> y; cur.init(n); for (int i = 1; i <= m; i++) { if (p[i][2] >= y) { cur.merge(p[i][0], p[i][1]); } } cout << cur.sze[cur.find(x)] << '\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...