#include <bits/stdc++.h>
using i64 = long long;
constexpr int maxN = 5E4 + 5;
std::vector<std::pair<int, int>> operations;
int par[maxN], sz[maxN];
void reset() {
std::iota(par, par + maxN, 0);
std::fill(sz, sz + maxN, 1);
operations.clear();
}
int get(int a) {
if(par[a] == a) {
return a;
}
return get(par[a]);
}
bool unite(int u, int v) {
u = get(u), v = get(v);
if(u == v) {
return false;
}
if(sz[u] > sz[v]) {
std::swap(u, v);
}
par[u] = v;
sz[v] += sz[u];
operations.emplace_back(u, v);
return true;
}
void rollback() {
auto [u, v] = operations.back();
operations.pop_back();
par[u] = u;
sz[v] -= sz[u];
}
int size(int a) {
return sz[get(a)];
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<bool> changed;
std::vector<int> u(m), v(m), w(m);
for(int i = 0; i < m; i++) {
std::cin >> u[i] >> v[i] >> w[i];
u[i]--, v[i]--;
}
int q;
std::cin >> q;
std::vector<int> t(q), x(q), y(q);
for(int i = 0; i < q; i++) {
std::cin >> t[i] >> x[i] >> y[i];
x[i]--;
}
constexpr int B = 350;
std::vector<std::vector<int>> deck(q);
std::vector<int> ans(q);
for(int l = 0; l < q; l += B) {
int r = std::min(q, l + B);
changed.assign(m, false);
reset();
std::vector<int> ask;
for(int i = l; i < r; i++) {
if(t[i] == 1) {
changed[x[i]] = true;
} else {
ask.emplace_back(i);
}
}
std::vector<int> edges, able;
for(int i = 0; i < m; i++) {
if(!changed[i]) {
edges.emplace_back(i);
} else {
able.emplace_back(i);
}
}
for(int i = l; i < r; i++) {
if(t[i] == 1) {
w[x[i]] = y[i];
} else {
for(int j : able) {
if(y[i] <= w[j]) {
deck[i].emplace_back(j);
}
}
}
}
std::sort(edges.begin(), edges.end(), [&](int lhs, int rhs) -> bool {
return w[lhs] > w[rhs];
});
std::sort(ask.begin(), ask.end(), [&](int lhs, int rhs) -> bool {
return y[lhs] > y[rhs];
});
int p = 0;
for(int i : ask) {
while(p != edges.size() && w[edges[p]] >= y[i]) {
unite(u[edges[p]], v[edges[p]]);
p++;
}
int ps = operations.size();
for(int j : deck[i]) {
unite(u[j], v[j]);
}
ans[i] = size(x[i]);
while(operations.size() != ps) {
rollback();
}
deck[i].clear();
}
}
for(int i = 0; i < q; i++) {
if(t[i] == 2) {
std::cout << ans[i] << '\n';
}
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | while(p != edges.size() && w[edges[p]] >= y[i]) {
| ~~^~~~~~~~~~~~~~~
bridges.cpp:125:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
125 | while(operations.size() != ps) {
| ~~~~~~~~~~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
16 ms |
3672 KB |
Output is correct |
4 |
Correct |
4 ms |
1372 KB |
Output is correct |
5 |
Correct |
9 ms |
2744 KB |
Output is correct |
6 |
Correct |
8 ms |
2648 KB |
Output is correct |
7 |
Correct |
8 ms |
2648 KB |
Output is correct |
8 |
Correct |
9 ms |
2392 KB |
Output is correct |
9 |
Correct |
9 ms |
3676 KB |
Output is correct |
10 |
Correct |
9 ms |
2652 KB |
Output is correct |
11 |
Correct |
9 ms |
2652 KB |
Output is correct |
12 |
Correct |
10 ms |
2908 KB |
Output is correct |
13 |
Correct |
11 ms |
2908 KB |
Output is correct |
14 |
Correct |
11 ms |
2772 KB |
Output is correct |
15 |
Correct |
12 ms |
2652 KB |
Output is correct |
16 |
Correct |
13 ms |
3164 KB |
Output is correct |
17 |
Correct |
12 ms |
2904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1608 ms |
35092 KB |
Output is correct |
2 |
Correct |
1583 ms |
34864 KB |
Output is correct |
3 |
Correct |
1621 ms |
35076 KB |
Output is correct |
4 |
Correct |
1550 ms |
34948 KB |
Output is correct |
5 |
Correct |
1564 ms |
35024 KB |
Output is correct |
6 |
Correct |
1665 ms |
59248 KB |
Output is correct |
7 |
Correct |
1613 ms |
59620 KB |
Output is correct |
8 |
Correct |
1602 ms |
59364 KB |
Output is correct |
9 |
Correct |
35 ms |
6224 KB |
Output is correct |
10 |
Correct |
651 ms |
45908 KB |
Output is correct |
11 |
Correct |
700 ms |
38868 KB |
Output is correct |
12 |
Correct |
1547 ms |
29180 KB |
Output is correct |
13 |
Correct |
1521 ms |
29100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1053 ms |
34204 KB |
Output is correct |
2 |
Correct |
373 ms |
44944 KB |
Output is correct |
3 |
Correct |
1076 ms |
46408 KB |
Output is correct |
4 |
Correct |
1061 ms |
34208 KB |
Output is correct |
5 |
Correct |
41 ms |
6140 KB |
Output is correct |
6 |
Correct |
1056 ms |
42248 KB |
Output is correct |
7 |
Correct |
1004 ms |
30440 KB |
Output is correct |
8 |
Correct |
1043 ms |
24364 KB |
Output is correct |
9 |
Correct |
979 ms |
20652 KB |
Output is correct |
10 |
Correct |
984 ms |
16840 KB |
Output is correct |
11 |
Correct |
968 ms |
19876 KB |
Output is correct |
12 |
Correct |
950 ms |
16012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3039 ms |
11448 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1608 ms |
35092 KB |
Output is correct |
2 |
Correct |
1583 ms |
34864 KB |
Output is correct |
3 |
Correct |
1621 ms |
35076 KB |
Output is correct |
4 |
Correct |
1550 ms |
34948 KB |
Output is correct |
5 |
Correct |
1564 ms |
35024 KB |
Output is correct |
6 |
Correct |
1665 ms |
59248 KB |
Output is correct |
7 |
Correct |
1613 ms |
59620 KB |
Output is correct |
8 |
Correct |
1602 ms |
59364 KB |
Output is correct |
9 |
Correct |
35 ms |
6224 KB |
Output is correct |
10 |
Correct |
651 ms |
45908 KB |
Output is correct |
11 |
Correct |
700 ms |
38868 KB |
Output is correct |
12 |
Correct |
1547 ms |
29180 KB |
Output is correct |
13 |
Correct |
1521 ms |
29100 KB |
Output is correct |
14 |
Correct |
1053 ms |
34204 KB |
Output is correct |
15 |
Correct |
373 ms |
44944 KB |
Output is correct |
16 |
Correct |
1076 ms |
46408 KB |
Output is correct |
17 |
Correct |
1061 ms |
34208 KB |
Output is correct |
18 |
Correct |
41 ms |
6140 KB |
Output is correct |
19 |
Correct |
1056 ms |
42248 KB |
Output is correct |
20 |
Correct |
1004 ms |
30440 KB |
Output is correct |
21 |
Correct |
1043 ms |
24364 KB |
Output is correct |
22 |
Correct |
979 ms |
20652 KB |
Output is correct |
23 |
Correct |
984 ms |
16840 KB |
Output is correct |
24 |
Correct |
968 ms |
19876 KB |
Output is correct |
25 |
Correct |
950 ms |
16012 KB |
Output is correct |
26 |
Correct |
1756 ms |
35004 KB |
Output is correct |
27 |
Correct |
1772 ms |
47388 KB |
Output is correct |
28 |
Correct |
1765 ms |
34484 KB |
Output is correct |
29 |
Correct |
1653 ms |
17704 KB |
Output is correct |
30 |
Correct |
1708 ms |
41396 KB |
Output is correct |
31 |
Correct |
1718 ms |
42716 KB |
Output is correct |
32 |
Correct |
1719 ms |
42796 KB |
Output is correct |
33 |
Correct |
1677 ms |
34180 KB |
Output is correct |
34 |
Correct |
1722 ms |
34356 KB |
Output is correct |
35 |
Correct |
1683 ms |
34308 KB |
Output is correct |
36 |
Correct |
1617 ms |
20396 KB |
Output is correct |
37 |
Correct |
1617 ms |
19740 KB |
Output is correct |
38 |
Correct |
1634 ms |
19256 KB |
Output is correct |
39 |
Correct |
1587 ms |
13816 KB |
Output is correct |
40 |
Correct |
1575 ms |
13544 KB |
Output is correct |
41 |
Correct |
1577 ms |
13328 KB |
Output is correct |
42 |
Correct |
1515 ms |
13140 KB |
Output is correct |
43 |
Correct |
1550 ms |
12832 KB |
Output is correct |
44 |
Correct |
1507 ms |
12448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
16 ms |
3672 KB |
Output is correct |
4 |
Correct |
4 ms |
1372 KB |
Output is correct |
5 |
Correct |
9 ms |
2744 KB |
Output is correct |
6 |
Correct |
8 ms |
2648 KB |
Output is correct |
7 |
Correct |
8 ms |
2648 KB |
Output is correct |
8 |
Correct |
9 ms |
2392 KB |
Output is correct |
9 |
Correct |
9 ms |
3676 KB |
Output is correct |
10 |
Correct |
9 ms |
2652 KB |
Output is correct |
11 |
Correct |
9 ms |
2652 KB |
Output is correct |
12 |
Correct |
10 ms |
2908 KB |
Output is correct |
13 |
Correct |
11 ms |
2908 KB |
Output is correct |
14 |
Correct |
11 ms |
2772 KB |
Output is correct |
15 |
Correct |
12 ms |
2652 KB |
Output is correct |
16 |
Correct |
13 ms |
3164 KB |
Output is correct |
17 |
Correct |
12 ms |
2904 KB |
Output is correct |
18 |
Correct |
1608 ms |
35092 KB |
Output is correct |
19 |
Correct |
1583 ms |
34864 KB |
Output is correct |
20 |
Correct |
1621 ms |
35076 KB |
Output is correct |
21 |
Correct |
1550 ms |
34948 KB |
Output is correct |
22 |
Correct |
1564 ms |
35024 KB |
Output is correct |
23 |
Correct |
1665 ms |
59248 KB |
Output is correct |
24 |
Correct |
1613 ms |
59620 KB |
Output is correct |
25 |
Correct |
1602 ms |
59364 KB |
Output is correct |
26 |
Correct |
35 ms |
6224 KB |
Output is correct |
27 |
Correct |
651 ms |
45908 KB |
Output is correct |
28 |
Correct |
700 ms |
38868 KB |
Output is correct |
29 |
Correct |
1547 ms |
29180 KB |
Output is correct |
30 |
Correct |
1521 ms |
29100 KB |
Output is correct |
31 |
Correct |
1053 ms |
34204 KB |
Output is correct |
32 |
Correct |
373 ms |
44944 KB |
Output is correct |
33 |
Correct |
1076 ms |
46408 KB |
Output is correct |
34 |
Correct |
1061 ms |
34208 KB |
Output is correct |
35 |
Correct |
41 ms |
6140 KB |
Output is correct |
36 |
Correct |
1056 ms |
42248 KB |
Output is correct |
37 |
Correct |
1004 ms |
30440 KB |
Output is correct |
38 |
Correct |
1043 ms |
24364 KB |
Output is correct |
39 |
Correct |
979 ms |
20652 KB |
Output is correct |
40 |
Correct |
984 ms |
16840 KB |
Output is correct |
41 |
Correct |
968 ms |
19876 KB |
Output is correct |
42 |
Correct |
950 ms |
16012 KB |
Output is correct |
43 |
Execution timed out |
3039 ms |
11448 KB |
Time limit exceeded |
44 |
Halted |
0 ms |
0 KB |
- |