#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ld long double
#define ll long long
mt19937 rnd(51);
const int N = 50010, K = 800, M = 1e5 + 10, INF = 1e9;
int par[N], sz[N], Sz = 0;
bool used[M], ed[M];
array<int, 4> arr[M];
int find_set(int v) {
while (v != par[v]) {
v = par[v];
}
return v;
}
void union_set(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a == b) return;
if (sz[a] < sz[b]) {
swap(a, b);
}
arr[Sz++] = {b, par[b], a, sz[a]};
par[b] = a;
sz[a] += sz[b];
}
void upd(int n) {
while (Sz > n) {
auto mas = arr[--Sz];
par[mas[0]] = mas[1];
sz[mas[2]] = mas[3];
}
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LCOAL
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < N; i++) {
sz[i] = 1;
par[i] = i;
}
int n, m;
cin >> n >> m;
vector<pair<int,int>> e(m);
vector<int> w(m);
for (int i = 0; i < m; i++) {
cin >> e[i].first >> e[i].second >> w[i];
e[i].first--, e[i].second--;
}
int q;
cin >> q;
vector<array<int, 3>> u(q);
vector<int> ans(q, -1);
for (int i = 0; i < q; ++i) {
cin >> u[i][0] >> u[i][1] >> u[i][2];
u[i][1]--;
}
for (int i = 0; i < q; i += K) {
vector<array<int, 3>> qu;
for (int j = i; j < min(i + K, q); ++j) {
if (u[j][0] == 1) {
used[u[j][1]] = 1;
} else {
qu.pb({u[j][2], u[j][1], j});
}
}
vector<int> a, b;
for (int j = 0; j < m; ++j) {
if (!used[j]) {
a.pb(j);
} else {
b.pb(j);
}
}
sort(a.begin(), a.end(), [&](int i, int j){return w[i] > w[j];});
sort(qu.rbegin(), qu.rend());
int ind = 0;
for (int j = 0; j < qu.size(); ++j) {
while (ind < a.size() && w[a[ind]] >= qu[j][0]) {
union_set(e[a[ind]].first, e[a[ind]].second);
ind++;
}
int was = Sz;
for (int f = qu[j][2]; f >= i; --f) {
if (u[f][0] == 1 && !ed[u[f][1]]) {
ed[u[f][1]] = 1;
if (u[f][2] >= qu[j][0]) {
union_set(e[u[f][1]].first, e[u[f][1]].second);
}
}
}
for (auto to : b) {
if (!ed[to]) {
if (w[to] >= qu[j][0]) {
union_set(e[to].first, e[to].second);
}
}
}
ans[qu[j][2]] = sz[find_set(qu[j][1])];
upd(was);
for (int f = qu[j][2]; f >= i; --f) {
if (u[f][0] == 1) {
ed[u[f][1]] = 0;
}
}
}
upd(0);
for (int j = i; j < min(i + K, q); ++j) {
if (u[j][0] == 1) {
used[u[j][1]] = 0;
w[u[j][1]] = u[j][2];
}
}
}
for (int i = 0; i < q; i++) {
if (ans[i] != -1) {
cout << ans[i] << '\n';
}
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j = 0; j < qu.size(); ++j) {
| ~~^~~~~~~~~~~
bridges.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while (ind < a.size() && w[a[ind]] >= qu[j][0]) {
| ~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
34 ms |
916 KB |
Output is correct |
4 |
Correct |
11 ms |
964 KB |
Output is correct |
5 |
Correct |
28 ms |
900 KB |
Output is correct |
6 |
Correct |
33 ms |
904 KB |
Output is correct |
7 |
Correct |
28 ms |
888 KB |
Output is correct |
8 |
Correct |
25 ms |
900 KB |
Output is correct |
9 |
Correct |
31 ms |
888 KB |
Output is correct |
10 |
Correct |
27 ms |
852 KB |
Output is correct |
11 |
Correct |
24 ms |
904 KB |
Output is correct |
12 |
Correct |
26 ms |
852 KB |
Output is correct |
13 |
Correct |
34 ms |
904 KB |
Output is correct |
14 |
Correct |
35 ms |
900 KB |
Output is correct |
15 |
Correct |
36 ms |
888 KB |
Output is correct |
16 |
Correct |
28 ms |
852 KB |
Output is correct |
17 |
Correct |
27 ms |
904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1543 ms |
4620 KB |
Output is correct |
2 |
Correct |
1564 ms |
4348 KB |
Output is correct |
3 |
Correct |
1590 ms |
4368 KB |
Output is correct |
4 |
Correct |
1590 ms |
4600 KB |
Output is correct |
5 |
Correct |
1589 ms |
4236 KB |
Output is correct |
6 |
Correct |
2093 ms |
4284 KB |
Output is correct |
7 |
Correct |
2055 ms |
4540 KB |
Output is correct |
8 |
Correct |
2067 ms |
4556 KB |
Output is correct |
9 |
Correct |
96 ms |
2428 KB |
Output is correct |
10 |
Correct |
1171 ms |
4300 KB |
Output is correct |
11 |
Correct |
1113 ms |
4256 KB |
Output is correct |
12 |
Correct |
1389 ms |
4520 KB |
Output is correct |
13 |
Correct |
1337 ms |
4324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1143 ms |
3708 KB |
Output is correct |
2 |
Correct |
765 ms |
2764 KB |
Output is correct |
3 |
Correct |
1275 ms |
3776 KB |
Output is correct |
4 |
Correct |
1121 ms |
3528 KB |
Output is correct |
5 |
Correct |
103 ms |
2476 KB |
Output is correct |
6 |
Correct |
1200 ms |
3528 KB |
Output is correct |
7 |
Correct |
995 ms |
3636 KB |
Output is correct |
8 |
Correct |
947 ms |
3768 KB |
Output is correct |
9 |
Correct |
796 ms |
3684 KB |
Output is correct |
10 |
Correct |
757 ms |
3784 KB |
Output is correct |
11 |
Correct |
742 ms |
3592 KB |
Output is correct |
12 |
Correct |
698 ms |
3548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1926 ms |
5540 KB |
Output is correct |
2 |
Correct |
110 ms |
2480 KB |
Output is correct |
3 |
Correct |
194 ms |
3096 KB |
Output is correct |
4 |
Correct |
90 ms |
3048 KB |
Output is correct |
5 |
Correct |
1016 ms |
5176 KB |
Output is correct |
6 |
Correct |
1855 ms |
5328 KB |
Output is correct |
7 |
Correct |
1018 ms |
5204 KB |
Output is correct |
8 |
Correct |
954 ms |
4196 KB |
Output is correct |
9 |
Correct |
943 ms |
4260 KB |
Output is correct |
10 |
Correct |
959 ms |
4348 KB |
Output is correct |
11 |
Correct |
1444 ms |
4996 KB |
Output is correct |
12 |
Correct |
1430 ms |
4780 KB |
Output is correct |
13 |
Correct |
1444 ms |
4832 KB |
Output is correct |
14 |
Correct |
932 ms |
5152 KB |
Output is correct |
15 |
Correct |
964 ms |
5256 KB |
Output is correct |
16 |
Correct |
1868 ms |
5364 KB |
Output is correct |
17 |
Correct |
1884 ms |
5252 KB |
Output is correct |
18 |
Correct |
1875 ms |
5424 KB |
Output is correct |
19 |
Correct |
1843 ms |
5492 KB |
Output is correct |
20 |
Correct |
1583 ms |
5084 KB |
Output is correct |
21 |
Correct |
1609 ms |
5156 KB |
Output is correct |
22 |
Correct |
1801 ms |
5244 KB |
Output is correct |
23 |
Correct |
1102 ms |
4820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1543 ms |
4620 KB |
Output is correct |
2 |
Correct |
1564 ms |
4348 KB |
Output is correct |
3 |
Correct |
1590 ms |
4368 KB |
Output is correct |
4 |
Correct |
1590 ms |
4600 KB |
Output is correct |
5 |
Correct |
1589 ms |
4236 KB |
Output is correct |
6 |
Correct |
2093 ms |
4284 KB |
Output is correct |
7 |
Correct |
2055 ms |
4540 KB |
Output is correct |
8 |
Correct |
2067 ms |
4556 KB |
Output is correct |
9 |
Correct |
96 ms |
2428 KB |
Output is correct |
10 |
Correct |
1171 ms |
4300 KB |
Output is correct |
11 |
Correct |
1113 ms |
4256 KB |
Output is correct |
12 |
Correct |
1389 ms |
4520 KB |
Output is correct |
13 |
Correct |
1337 ms |
4324 KB |
Output is correct |
14 |
Correct |
1143 ms |
3708 KB |
Output is correct |
15 |
Correct |
765 ms |
2764 KB |
Output is correct |
16 |
Correct |
1275 ms |
3776 KB |
Output is correct |
17 |
Correct |
1121 ms |
3528 KB |
Output is correct |
18 |
Correct |
103 ms |
2476 KB |
Output is correct |
19 |
Correct |
1200 ms |
3528 KB |
Output is correct |
20 |
Correct |
995 ms |
3636 KB |
Output is correct |
21 |
Correct |
947 ms |
3768 KB |
Output is correct |
22 |
Correct |
796 ms |
3684 KB |
Output is correct |
23 |
Correct |
757 ms |
3784 KB |
Output is correct |
24 |
Correct |
742 ms |
3592 KB |
Output is correct |
25 |
Correct |
698 ms |
3548 KB |
Output is correct |
26 |
Correct |
1399 ms |
4356 KB |
Output is correct |
27 |
Correct |
1680 ms |
4508 KB |
Output is correct |
28 |
Correct |
1486 ms |
4396 KB |
Output is correct |
29 |
Correct |
1201 ms |
4240 KB |
Output is correct |
30 |
Correct |
1665 ms |
4452 KB |
Output is correct |
31 |
Correct |
1691 ms |
4340 KB |
Output is correct |
32 |
Correct |
1689 ms |
4404 KB |
Output is correct |
33 |
Correct |
1496 ms |
4440 KB |
Output is correct |
34 |
Correct |
1478 ms |
4232 KB |
Output is correct |
35 |
Correct |
1504 ms |
4496 KB |
Output is correct |
36 |
Correct |
1253 ms |
4320 KB |
Output is correct |
37 |
Correct |
1250 ms |
4268 KB |
Output is correct |
38 |
Correct |
1260 ms |
4304 KB |
Output is correct |
39 |
Correct |
1102 ms |
4224 KB |
Output is correct |
40 |
Correct |
1098 ms |
4456 KB |
Output is correct |
41 |
Correct |
1074 ms |
4236 KB |
Output is correct |
42 |
Correct |
1002 ms |
4320 KB |
Output is correct |
43 |
Correct |
1012 ms |
4312 KB |
Output is correct |
44 |
Correct |
997 ms |
4208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
34 ms |
916 KB |
Output is correct |
4 |
Correct |
11 ms |
964 KB |
Output is correct |
5 |
Correct |
28 ms |
900 KB |
Output is correct |
6 |
Correct |
33 ms |
904 KB |
Output is correct |
7 |
Correct |
28 ms |
888 KB |
Output is correct |
8 |
Correct |
25 ms |
900 KB |
Output is correct |
9 |
Correct |
31 ms |
888 KB |
Output is correct |
10 |
Correct |
27 ms |
852 KB |
Output is correct |
11 |
Correct |
24 ms |
904 KB |
Output is correct |
12 |
Correct |
26 ms |
852 KB |
Output is correct |
13 |
Correct |
34 ms |
904 KB |
Output is correct |
14 |
Correct |
35 ms |
900 KB |
Output is correct |
15 |
Correct |
36 ms |
888 KB |
Output is correct |
16 |
Correct |
28 ms |
852 KB |
Output is correct |
17 |
Correct |
27 ms |
904 KB |
Output is correct |
18 |
Correct |
1543 ms |
4620 KB |
Output is correct |
19 |
Correct |
1564 ms |
4348 KB |
Output is correct |
20 |
Correct |
1590 ms |
4368 KB |
Output is correct |
21 |
Correct |
1590 ms |
4600 KB |
Output is correct |
22 |
Correct |
1589 ms |
4236 KB |
Output is correct |
23 |
Correct |
2093 ms |
4284 KB |
Output is correct |
24 |
Correct |
2055 ms |
4540 KB |
Output is correct |
25 |
Correct |
2067 ms |
4556 KB |
Output is correct |
26 |
Correct |
96 ms |
2428 KB |
Output is correct |
27 |
Correct |
1171 ms |
4300 KB |
Output is correct |
28 |
Correct |
1113 ms |
4256 KB |
Output is correct |
29 |
Correct |
1389 ms |
4520 KB |
Output is correct |
30 |
Correct |
1337 ms |
4324 KB |
Output is correct |
31 |
Correct |
1143 ms |
3708 KB |
Output is correct |
32 |
Correct |
765 ms |
2764 KB |
Output is correct |
33 |
Correct |
1275 ms |
3776 KB |
Output is correct |
34 |
Correct |
1121 ms |
3528 KB |
Output is correct |
35 |
Correct |
103 ms |
2476 KB |
Output is correct |
36 |
Correct |
1200 ms |
3528 KB |
Output is correct |
37 |
Correct |
995 ms |
3636 KB |
Output is correct |
38 |
Correct |
947 ms |
3768 KB |
Output is correct |
39 |
Correct |
796 ms |
3684 KB |
Output is correct |
40 |
Correct |
757 ms |
3784 KB |
Output is correct |
41 |
Correct |
742 ms |
3592 KB |
Output is correct |
42 |
Correct |
698 ms |
3548 KB |
Output is correct |
43 |
Correct |
1926 ms |
5540 KB |
Output is correct |
44 |
Correct |
110 ms |
2480 KB |
Output is correct |
45 |
Correct |
194 ms |
3096 KB |
Output is correct |
46 |
Correct |
90 ms |
3048 KB |
Output is correct |
47 |
Correct |
1016 ms |
5176 KB |
Output is correct |
48 |
Correct |
1855 ms |
5328 KB |
Output is correct |
49 |
Correct |
1018 ms |
5204 KB |
Output is correct |
50 |
Correct |
954 ms |
4196 KB |
Output is correct |
51 |
Correct |
943 ms |
4260 KB |
Output is correct |
52 |
Correct |
959 ms |
4348 KB |
Output is correct |
53 |
Correct |
1444 ms |
4996 KB |
Output is correct |
54 |
Correct |
1430 ms |
4780 KB |
Output is correct |
55 |
Correct |
1444 ms |
4832 KB |
Output is correct |
56 |
Correct |
932 ms |
5152 KB |
Output is correct |
57 |
Correct |
964 ms |
5256 KB |
Output is correct |
58 |
Correct |
1868 ms |
5364 KB |
Output is correct |
59 |
Correct |
1884 ms |
5252 KB |
Output is correct |
60 |
Correct |
1875 ms |
5424 KB |
Output is correct |
61 |
Correct |
1843 ms |
5492 KB |
Output is correct |
62 |
Correct |
1583 ms |
5084 KB |
Output is correct |
63 |
Correct |
1609 ms |
5156 KB |
Output is correct |
64 |
Correct |
1801 ms |
5244 KB |
Output is correct |
65 |
Correct |
1102 ms |
4820 KB |
Output is correct |
66 |
Correct |
1399 ms |
4356 KB |
Output is correct |
67 |
Correct |
1680 ms |
4508 KB |
Output is correct |
68 |
Correct |
1486 ms |
4396 KB |
Output is correct |
69 |
Correct |
1201 ms |
4240 KB |
Output is correct |
70 |
Correct |
1665 ms |
4452 KB |
Output is correct |
71 |
Correct |
1691 ms |
4340 KB |
Output is correct |
72 |
Correct |
1689 ms |
4404 KB |
Output is correct |
73 |
Correct |
1496 ms |
4440 KB |
Output is correct |
74 |
Correct |
1478 ms |
4232 KB |
Output is correct |
75 |
Correct |
1504 ms |
4496 KB |
Output is correct |
76 |
Correct |
1253 ms |
4320 KB |
Output is correct |
77 |
Correct |
1250 ms |
4268 KB |
Output is correct |
78 |
Correct |
1260 ms |
4304 KB |
Output is correct |
79 |
Correct |
1102 ms |
4224 KB |
Output is correct |
80 |
Correct |
1098 ms |
4456 KB |
Output is correct |
81 |
Correct |
1074 ms |
4236 KB |
Output is correct |
82 |
Correct |
1002 ms |
4320 KB |
Output is correct |
83 |
Correct |
1012 ms |
4312 KB |
Output is correct |
84 |
Correct |
997 ms |
4208 KB |
Output is correct |
85 |
Correct |
2287 ms |
5480 KB |
Output is correct |
86 |
Correct |
223 ms |
3164 KB |
Output is correct |
87 |
Correct |
126 ms |
3212 KB |
Output is correct |
88 |
Correct |
1419 ms |
5564 KB |
Output is correct |
89 |
Correct |
2323 ms |
5748 KB |
Output is correct |
90 |
Correct |
1434 ms |
5648 KB |
Output is correct |
91 |
Correct |
1571 ms |
4580 KB |
Output is correct |
92 |
Correct |
1506 ms |
4236 KB |
Output is correct |
93 |
Correct |
1998 ms |
4340 KB |
Output is correct |
94 |
Correct |
1916 ms |
4928 KB |
Output is correct |
95 |
Correct |
1887 ms |
5176 KB |
Output is correct |
96 |
Correct |
2095 ms |
5008 KB |
Output is correct |
97 |
Correct |
1136 ms |
5252 KB |
Output is correct |
98 |
Correct |
1151 ms |
5300 KB |
Output is correct |
99 |
Correct |
2304 ms |
6136 KB |
Output is correct |
100 |
Correct |
2329 ms |
5616 KB |
Output is correct |
101 |
Correct |
2336 ms |
5588 KB |
Output is correct |
102 |
Correct |
2320 ms |
5348 KB |
Output is correct |
103 |
Correct |
2244 ms |
5240 KB |
Output is correct |
104 |
Correct |
2224 ms |
5372 KB |
Output is correct |
105 |
Correct |
1933 ms |
5148 KB |
Output is correct |
106 |
Correct |
1766 ms |
4956 KB |
Output is correct |
107 |
Correct |
1995 ms |
5120 KB |
Output is correct |
108 |
Correct |
2337 ms |
5168 KB |
Output is correct |
109 |
Correct |
1564 ms |
4932 KB |
Output is correct |