#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;
const int BLOCK = 1000;
int N, M, Q; int U[MX], V[MX], W[MX]; int T[MX], X[MX], Y[MX];
bool seen[MX];
vi join[BLOCK]; int ans[MX];
int par[50010], sz[50010]; stack<int> stck;
int find(int A) { return (A == par[A]) ? A : find(par[A]); }
void onion(int A, int B) {
A = find(A); B = find(B); if (A == B) return ;
if (sz[A] < sz[B]) swap(A, B); stck.push(B); par[B] = A; sz[A] += sz[B];
}
void rollback(int SZ) {
while (sz(stck) > SZ) {
int cur = stck.top(); stck.pop();
sz[par[cur]] -= sz[cur]; par[cur] = cur;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> M; FOR(i, 1, M + 1) cin >> U[i] >> V[i] >> W[i]; // 1-indexed Edges
cin >> Q; F0R(i, Q) cin >> T[i] >> X[i] >> Y[i];
for (int i = 0; i < Q; i += BLOCK) {
int j = min(Q, i + BLOCK); // Right endpoint of current block
FOR(k, 1, N + 1) par[k] = k, sz[k] = 1;
vi changed, unchanged, query;
FOR(k, 1, M + 1) seen[k] = false;
FOR(k, i, j) {
if (T[k] == 1) { changed.pb(k); seen[X[k]] = true; }
else { query.pb(k); }
}
FOR(k, 1, M + 1) if (!seen[k]) unchanged.pb(k);
FOR(k, i, j) {
if (T[k] == 1) { W[X[k]] = Y[k]; }
else {
join[k - i].clear();
EACH(C, changed) if (W[X[C]] >= Y[k]) join[k - i].pb(X[C]);
}
}
sort(all(unchanged), [](int a, int b) { return W[a] > W[b]; });
sort(all(query), [](int a, int b) { return Y[a] > Y[b]; });
int ptr = 0;
EACH(C, query) {
while (ptr < sz(unchanged) && W[unchanged[ptr]] >= Y[C]) {
onion(U[unchanged[ptr]], V[unchanged[ptr]]); ptr++;
}
int SZ = sz(stck);
EACH(nxt, join[C - i]) onion(U[nxt], V[nxt]);
ans[C] = sz[find(X[C])]; rollback(SZ);
}
}
F0R(i, Q) if (T[i] == 2) cout << ans[i] << "\n";
}
Compilation message
bridges.cpp: In function 'void onion(int, int)':
bridges.cpp:66:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
66 | if (sz[A] < sz[B]) swap(A, B); stck.push(B); par[B] = A; sz[A] += sz[B];
| ^~
bridges.cpp:66:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
66 | if (sz[A] < sz[B]) swap(A, B); stck.push(B); par[B] = A; sz[A] += sz[B];
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
51 ms |
2612 KB |
Output is correct |
4 |
Correct |
7 ms |
460 KB |
Output is correct |
5 |
Correct |
42 ms |
2784 KB |
Output is correct |
6 |
Correct |
32 ms |
2588 KB |
Output is correct |
7 |
Correct |
38 ms |
3460 KB |
Output is correct |
8 |
Correct |
42 ms |
2596 KB |
Output is correct |
9 |
Correct |
48 ms |
4208 KB |
Output is correct |
10 |
Correct |
43 ms |
2680 KB |
Output is correct |
11 |
Correct |
43 ms |
2636 KB |
Output is correct |
12 |
Correct |
52 ms |
2756 KB |
Output is correct |
13 |
Correct |
49 ms |
2744 KB |
Output is correct |
14 |
Correct |
45 ms |
2648 KB |
Output is correct |
15 |
Correct |
51 ms |
2700 KB |
Output is correct |
16 |
Correct |
46 ms |
4064 KB |
Output is correct |
17 |
Correct |
46 ms |
3436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1512 ms |
26088 KB |
Output is correct |
2 |
Correct |
1494 ms |
26044 KB |
Output is correct |
3 |
Correct |
1467 ms |
26060 KB |
Output is correct |
4 |
Correct |
1522 ms |
25972 KB |
Output is correct |
5 |
Correct |
1526 ms |
26348 KB |
Output is correct |
6 |
Correct |
2336 ms |
27900 KB |
Output is correct |
7 |
Correct |
2242 ms |
27816 KB |
Output is correct |
8 |
Correct |
2240 ms |
27812 KB |
Output is correct |
9 |
Correct |
43 ms |
1988 KB |
Output is correct |
10 |
Correct |
1281 ms |
27876 KB |
Output is correct |
11 |
Correct |
1182 ms |
27852 KB |
Output is correct |
12 |
Correct |
1279 ms |
24692 KB |
Output is correct |
13 |
Correct |
1301 ms |
27416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1193 ms |
18732 KB |
Output is correct |
2 |
Correct |
893 ms |
9736 KB |
Output is correct |
3 |
Correct |
1390 ms |
20424 KB |
Output is correct |
4 |
Correct |
1145 ms |
18768 KB |
Output is correct |
5 |
Correct |
43 ms |
1988 KB |
Output is correct |
6 |
Correct |
1319 ms |
18776 KB |
Output is correct |
7 |
Correct |
1042 ms |
18340 KB |
Output is correct |
8 |
Correct |
931 ms |
18260 KB |
Output is correct |
9 |
Correct |
760 ms |
17076 KB |
Output is correct |
10 |
Correct |
701 ms |
17008 KB |
Output is correct |
11 |
Correct |
807 ms |
19840 KB |
Output is correct |
12 |
Correct |
698 ms |
19784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1754 ms |
24792 KB |
Output is correct |
2 |
Correct |
53 ms |
3396 KB |
Output is correct |
3 |
Correct |
178 ms |
4544 KB |
Output is correct |
4 |
Correct |
92 ms |
4836 KB |
Output is correct |
5 |
Correct |
860 ms |
27176 KB |
Output is correct |
6 |
Correct |
1690 ms |
28732 KB |
Output is correct |
7 |
Correct |
874 ms |
27084 KB |
Output is correct |
8 |
Correct |
813 ms |
26544 KB |
Output is correct |
9 |
Correct |
813 ms |
26724 KB |
Output is correct |
10 |
Correct |
818 ms |
26580 KB |
Output is correct |
11 |
Correct |
1304 ms |
27844 KB |
Output is correct |
12 |
Correct |
1234 ms |
27956 KB |
Output is correct |
13 |
Correct |
1267 ms |
28060 KB |
Output is correct |
14 |
Correct |
773 ms |
27120 KB |
Output is correct |
15 |
Correct |
825 ms |
27176 KB |
Output is correct |
16 |
Correct |
1693 ms |
28952 KB |
Output is correct |
17 |
Correct |
1689 ms |
28788 KB |
Output is correct |
18 |
Correct |
1672 ms |
29156 KB |
Output is correct |
19 |
Correct |
1679 ms |
29020 KB |
Output is correct |
20 |
Correct |
1410 ms |
28260 KB |
Output is correct |
21 |
Correct |
1385 ms |
28308 KB |
Output is correct |
22 |
Correct |
1614 ms |
28412 KB |
Output is correct |
23 |
Correct |
946 ms |
24984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1512 ms |
26088 KB |
Output is correct |
2 |
Correct |
1494 ms |
26044 KB |
Output is correct |
3 |
Correct |
1467 ms |
26060 KB |
Output is correct |
4 |
Correct |
1522 ms |
25972 KB |
Output is correct |
5 |
Correct |
1526 ms |
26348 KB |
Output is correct |
6 |
Correct |
2336 ms |
27900 KB |
Output is correct |
7 |
Correct |
2242 ms |
27816 KB |
Output is correct |
8 |
Correct |
2240 ms |
27812 KB |
Output is correct |
9 |
Correct |
43 ms |
1988 KB |
Output is correct |
10 |
Correct |
1281 ms |
27876 KB |
Output is correct |
11 |
Correct |
1182 ms |
27852 KB |
Output is correct |
12 |
Correct |
1279 ms |
24692 KB |
Output is correct |
13 |
Correct |
1301 ms |
27416 KB |
Output is correct |
14 |
Correct |
1193 ms |
18732 KB |
Output is correct |
15 |
Correct |
893 ms |
9736 KB |
Output is correct |
16 |
Correct |
1390 ms |
20424 KB |
Output is correct |
17 |
Correct |
1145 ms |
18768 KB |
Output is correct |
18 |
Correct |
43 ms |
1988 KB |
Output is correct |
19 |
Correct |
1319 ms |
18776 KB |
Output is correct |
20 |
Correct |
1042 ms |
18340 KB |
Output is correct |
21 |
Correct |
931 ms |
18260 KB |
Output is correct |
22 |
Correct |
760 ms |
17076 KB |
Output is correct |
23 |
Correct |
701 ms |
17008 KB |
Output is correct |
24 |
Correct |
807 ms |
19840 KB |
Output is correct |
25 |
Correct |
698 ms |
19784 KB |
Output is correct |
26 |
Correct |
1462 ms |
26256 KB |
Output is correct |
27 |
Correct |
1839 ms |
28020 KB |
Output is correct |
28 |
Correct |
1523 ms |
26256 KB |
Output is correct |
29 |
Correct |
1090 ms |
25600 KB |
Output is correct |
30 |
Correct |
1778 ms |
27772 KB |
Output is correct |
31 |
Correct |
1856 ms |
27920 KB |
Output is correct |
32 |
Correct |
1848 ms |
27944 KB |
Output is correct |
33 |
Correct |
1518 ms |
25996 KB |
Output is correct |
34 |
Correct |
1563 ms |
25988 KB |
Output is correct |
35 |
Correct |
1532 ms |
26184 KB |
Output is correct |
36 |
Correct |
1158 ms |
25884 KB |
Output is correct |
37 |
Correct |
1132 ms |
25772 KB |
Output is correct |
38 |
Correct |
1114 ms |
25744 KB |
Output is correct |
39 |
Correct |
929 ms |
24268 KB |
Output is correct |
40 |
Correct |
916 ms |
24392 KB |
Output is correct |
41 |
Correct |
934 ms |
24556 KB |
Output is correct |
42 |
Correct |
906 ms |
26436 KB |
Output is correct |
43 |
Correct |
911 ms |
26296 KB |
Output is correct |
44 |
Correct |
928 ms |
26152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
51 ms |
2612 KB |
Output is correct |
4 |
Correct |
7 ms |
460 KB |
Output is correct |
5 |
Correct |
42 ms |
2784 KB |
Output is correct |
6 |
Correct |
32 ms |
2588 KB |
Output is correct |
7 |
Correct |
38 ms |
3460 KB |
Output is correct |
8 |
Correct |
42 ms |
2596 KB |
Output is correct |
9 |
Correct |
48 ms |
4208 KB |
Output is correct |
10 |
Correct |
43 ms |
2680 KB |
Output is correct |
11 |
Correct |
43 ms |
2636 KB |
Output is correct |
12 |
Correct |
52 ms |
2756 KB |
Output is correct |
13 |
Correct |
49 ms |
2744 KB |
Output is correct |
14 |
Correct |
45 ms |
2648 KB |
Output is correct |
15 |
Correct |
51 ms |
2700 KB |
Output is correct |
16 |
Correct |
46 ms |
4064 KB |
Output is correct |
17 |
Correct |
46 ms |
3436 KB |
Output is correct |
18 |
Correct |
1512 ms |
26088 KB |
Output is correct |
19 |
Correct |
1494 ms |
26044 KB |
Output is correct |
20 |
Correct |
1467 ms |
26060 KB |
Output is correct |
21 |
Correct |
1522 ms |
25972 KB |
Output is correct |
22 |
Correct |
1526 ms |
26348 KB |
Output is correct |
23 |
Correct |
2336 ms |
27900 KB |
Output is correct |
24 |
Correct |
2242 ms |
27816 KB |
Output is correct |
25 |
Correct |
2240 ms |
27812 KB |
Output is correct |
26 |
Correct |
43 ms |
1988 KB |
Output is correct |
27 |
Correct |
1281 ms |
27876 KB |
Output is correct |
28 |
Correct |
1182 ms |
27852 KB |
Output is correct |
29 |
Correct |
1279 ms |
24692 KB |
Output is correct |
30 |
Correct |
1301 ms |
27416 KB |
Output is correct |
31 |
Correct |
1193 ms |
18732 KB |
Output is correct |
32 |
Correct |
893 ms |
9736 KB |
Output is correct |
33 |
Correct |
1390 ms |
20424 KB |
Output is correct |
34 |
Correct |
1145 ms |
18768 KB |
Output is correct |
35 |
Correct |
43 ms |
1988 KB |
Output is correct |
36 |
Correct |
1319 ms |
18776 KB |
Output is correct |
37 |
Correct |
1042 ms |
18340 KB |
Output is correct |
38 |
Correct |
931 ms |
18260 KB |
Output is correct |
39 |
Correct |
760 ms |
17076 KB |
Output is correct |
40 |
Correct |
701 ms |
17008 KB |
Output is correct |
41 |
Correct |
807 ms |
19840 KB |
Output is correct |
42 |
Correct |
698 ms |
19784 KB |
Output is correct |
43 |
Correct |
1754 ms |
24792 KB |
Output is correct |
44 |
Correct |
53 ms |
3396 KB |
Output is correct |
45 |
Correct |
178 ms |
4544 KB |
Output is correct |
46 |
Correct |
92 ms |
4836 KB |
Output is correct |
47 |
Correct |
860 ms |
27176 KB |
Output is correct |
48 |
Correct |
1690 ms |
28732 KB |
Output is correct |
49 |
Correct |
874 ms |
27084 KB |
Output is correct |
50 |
Correct |
813 ms |
26544 KB |
Output is correct |
51 |
Correct |
813 ms |
26724 KB |
Output is correct |
52 |
Correct |
818 ms |
26580 KB |
Output is correct |
53 |
Correct |
1304 ms |
27844 KB |
Output is correct |
54 |
Correct |
1234 ms |
27956 KB |
Output is correct |
55 |
Correct |
1267 ms |
28060 KB |
Output is correct |
56 |
Correct |
773 ms |
27120 KB |
Output is correct |
57 |
Correct |
825 ms |
27176 KB |
Output is correct |
58 |
Correct |
1693 ms |
28952 KB |
Output is correct |
59 |
Correct |
1689 ms |
28788 KB |
Output is correct |
60 |
Correct |
1672 ms |
29156 KB |
Output is correct |
61 |
Correct |
1679 ms |
29020 KB |
Output is correct |
62 |
Correct |
1410 ms |
28260 KB |
Output is correct |
63 |
Correct |
1385 ms |
28308 KB |
Output is correct |
64 |
Correct |
1614 ms |
28412 KB |
Output is correct |
65 |
Correct |
946 ms |
24984 KB |
Output is correct |
66 |
Correct |
1462 ms |
26256 KB |
Output is correct |
67 |
Correct |
1839 ms |
28020 KB |
Output is correct |
68 |
Correct |
1523 ms |
26256 KB |
Output is correct |
69 |
Correct |
1090 ms |
25600 KB |
Output is correct |
70 |
Correct |
1778 ms |
27772 KB |
Output is correct |
71 |
Correct |
1856 ms |
27920 KB |
Output is correct |
72 |
Correct |
1848 ms |
27944 KB |
Output is correct |
73 |
Correct |
1518 ms |
25996 KB |
Output is correct |
74 |
Correct |
1563 ms |
25988 KB |
Output is correct |
75 |
Correct |
1532 ms |
26184 KB |
Output is correct |
76 |
Correct |
1158 ms |
25884 KB |
Output is correct |
77 |
Correct |
1132 ms |
25772 KB |
Output is correct |
78 |
Correct |
1114 ms |
25744 KB |
Output is correct |
79 |
Correct |
929 ms |
24268 KB |
Output is correct |
80 |
Correct |
916 ms |
24392 KB |
Output is correct |
81 |
Correct |
934 ms |
24556 KB |
Output is correct |
82 |
Correct |
906 ms |
26436 KB |
Output is correct |
83 |
Correct |
911 ms |
26296 KB |
Output is correct |
84 |
Correct |
928 ms |
26152 KB |
Output is correct |
85 |
Correct |
2272 ms |
30760 KB |
Output is correct |
86 |
Correct |
215 ms |
6620 KB |
Output is correct |
87 |
Correct |
143 ms |
7928 KB |
Output is correct |
88 |
Correct |
1406 ms |
31044 KB |
Output is correct |
89 |
Correct |
2227 ms |
30980 KB |
Output is correct |
90 |
Correct |
1396 ms |
31156 KB |
Output is correct |
91 |
Correct |
1567 ms |
28828 KB |
Output is correct |
92 |
Correct |
1550 ms |
29048 KB |
Output is correct |
93 |
Correct |
2271 ms |
30328 KB |
Output is correct |
94 |
Correct |
1863 ms |
30404 KB |
Output is correct |
95 |
Correct |
1841 ms |
30452 KB |
Output is correct |
96 |
Correct |
2269 ms |
31988 KB |
Output is correct |
97 |
Correct |
1044 ms |
27660 KB |
Output is correct |
98 |
Correct |
1088 ms |
30748 KB |
Output is correct |
99 |
Correct |
2240 ms |
31236 KB |
Output is correct |
100 |
Correct |
2230 ms |
30952 KB |
Output is correct |
101 |
Correct |
2314 ms |
31380 KB |
Output is correct |
102 |
Correct |
2298 ms |
31324 KB |
Output is correct |
103 |
Correct |
2513 ms |
32244 KB |
Output is correct |
104 |
Correct |
2517 ms |
32284 KB |
Output is correct |
105 |
Correct |
1834 ms |
32032 KB |
Output is correct |
106 |
Correct |
1485 ms |
31536 KB |
Output is correct |
107 |
Correct |
1783 ms |
28768 KB |
Output is correct |
108 |
Correct |
2330 ms |
31044 KB |
Output is correct |
109 |
Correct |
1755 ms |
28988 KB |
Output is correct |