#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int K = 500;
const int MAXM = 100000;
const int MAXN = 50000;
int E[MAXM][3];
int par[MAXN];
int rk[MAXN];
int cur[MAXM];
int find(int x, bool alpha = true) {
if (par[x] == x) {
return x;
}
else {
if (!alpha) {
return find(par[x], false);
}
else {
return (par[x] = find(par[x]));
}
}
}
void merge(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
if (rk[py] > rk[px]) {
swap(px, py);
}
par[py] = px;
rk[px] += rk[py];
}
}
int dfMerge(vector<int>& arr, int i, int low, int a) {
if (i == arr.size()) {
return rk[find(a, false)];
}
else {
if (cur[arr[i]] >= low) {
int px = find(E[arr[i]][0], false);
int py = find(E[arr[i]][1], false);
if (px != py) {
if (rk[px] < rk[py]) {
swap(px, py);
}
par[py] = px;
rk[px] += rk[py];
int ans = dfMerge(arr, i+1, low, a);
par[py] = py;
rk[px] -= rk[py];
return ans;
}
else {
return dfMerge(arr, i+1, low, a);
}
}
else {
return dfMerge(arr, i+1, low, a);
}
}
}
int inChng[MAXM];
pair<int, int> to[MAXM];
struct Query {
int t, i, j;
};
Query qs[MAXM];
int ans[MAXM];
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N, M;
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> E[i][0] >> E[i][1] >> E[i][2];
E[i][0]--;
E[i][1]--;
cur[i] = E[i][2];
}
int Q;
cin >> Q;
FR(i, Q) {
cin >> qs[i].t >> qs[i].i >> qs[i].j;
qs[i].i--;
if (qs[i].t == 1) {
to[i].first = cur[qs[i].i];
to[i].second = qs[i].j;
cur[qs[i].i] = qs[i].j;
}
else {
to[i].first = -1;
}
}
FR(i, M) {
cur[i] = E[i][2];
}
int l = 0;
int r = -1;
fill(all(inChng), -K);
fill(all(ans), -1);
vector<int> other;
vector<int> nother;
other.resize(M);
nother.resize(M);
FR(i, M) {
other[i] = i;
}
auto comp = [&](const int& lhs, const int& rhs) {
return cur[lhs] > cur[rhs];
};
while (l < Q) {
sort(all(other), comp);
vector<int> changed;
vector<int> respond;
FR(i, N) {
par[i] = i;
rk[i] = 1;
}
for (int j = 0; l+j < Q && j < K; j++) {
if (qs[l+j].t == 1) {
if (inChng[qs[l+j].i] != l) {
changed.push_back(qs[l+j].i);
inChng[qs[l+j].i] = l;
}
}
else {
respond.push_back(l+j);
}
}
sort(all(respond), [] (const int& lhs, const int& rhs) {
return qs[lhs].j > qs[rhs].j;
});
int u = 0;
for (int next : respond) {
while (r < next) {
if (to[r+1].first != -1) {
cur[qs[r+1].i] = to[r+1].second;
}
r++;
}
while (r > next) {
if (to[r].first != -1) {
cur[qs[r].i] = to[r].first;
}
r--;
}
while (u < M && (inChng[other[u]] == l || cur[other[u]] >= qs[next].j)) {
if (inChng[other[u]] != l) {
merge(E[other[u]][0], E[other[u]][1]);
}
u++;
}
ans[r] = dfMerge(changed, 0, qs[next].j, qs[next].i);
}
l += K;
while (r < l-1 && r < Q-1) {
if (to[r+1].first != -1) {
cur[qs[r+1].i] = to[r+1].second;
}
r++;
}
sort(all(changed));
assert (changed.size() == unique(all(changed))-changed.begin());
sort(all(changed), comp);
int a = 0;
int b = 0;
for (int i = 0; i < M; i++) {
while (a < M && inChng[other[a]] == l-K) {
a++;
}
if (a == M) {
nother[i] = changed[b++];
}
else if (b == changed.size()) {
nother[i] = other[a++];
}
else {
if (cur[other[a]] > cur[changed[b]]) {
nother[i] = other[a++];
}
else {
nother[i] = changed[b++];
}
}
}
for (int i = 0; i < M; i++) {
other[i] = nother[i];
}
// for (int i = 1; i < M; i++) {
// assert (cur[other[i]] <= cur[other[i-1]]);
// }
}
for (int i = 0; i < Q; i++) {
if (ans[i] != -1) {
cout << ans[i] << '\n';
}
}
return 0;
}
Compilation message
bridges.cpp: In function 'int dfMerge(std::vector<int>&, int, int, int)':
bridges.cpp:44:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if (i == arr.size()) {
| ~~^~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from bridges.cpp:1:
bridges.cpp: In function 'int main()':
bridges.cpp:174:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} [-Wsign-compare]
174 | assert (changed.size() == unique(all(changed))-changed.begin());
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:185:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | else if (b == changed.size()) {
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
19 ms |
1388 KB |
Output is correct |
4 |
Correct |
7 ms |
1388 KB |
Output is correct |
5 |
Correct |
14 ms |
1388 KB |
Output is correct |
6 |
Correct |
11 ms |
1388 KB |
Output is correct |
7 |
Correct |
13 ms |
1388 KB |
Output is correct |
8 |
Correct |
15 ms |
1388 KB |
Output is correct |
9 |
Correct |
15 ms |
1388 KB |
Output is correct |
10 |
Correct |
15 ms |
1388 KB |
Output is correct |
11 |
Correct |
14 ms |
1388 KB |
Output is correct |
12 |
Correct |
18 ms |
1516 KB |
Output is correct |
13 |
Correct |
19 ms |
1388 KB |
Output is correct |
14 |
Correct |
18 ms |
1408 KB |
Output is correct |
15 |
Correct |
16 ms |
1388 KB |
Output is correct |
16 |
Correct |
15 ms |
1516 KB |
Output is correct |
17 |
Correct |
15 ms |
1388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1243 ms |
4716 KB |
Output is correct |
2 |
Correct |
1246 ms |
4724 KB |
Output is correct |
3 |
Correct |
1232 ms |
4740 KB |
Output is correct |
4 |
Correct |
1300 ms |
4844 KB |
Output is correct |
5 |
Correct |
1296 ms |
4716 KB |
Output is correct |
6 |
Correct |
1812 ms |
4972 KB |
Output is correct |
7 |
Correct |
1810 ms |
5100 KB |
Output is correct |
8 |
Correct |
1795 ms |
4972 KB |
Output is correct |
9 |
Correct |
62 ms |
3308 KB |
Output is correct |
10 |
Correct |
1325 ms |
4972 KB |
Output is correct |
11 |
Correct |
1234 ms |
4844 KB |
Output is correct |
12 |
Correct |
1225 ms |
5224 KB |
Output is correct |
13 |
Correct |
1200 ms |
4728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
871 ms |
4204 KB |
Output is correct |
2 |
Correct |
522 ms |
3564 KB |
Output is correct |
3 |
Correct |
970 ms |
4332 KB |
Output is correct |
4 |
Correct |
865 ms |
4464 KB |
Output is correct |
5 |
Correct |
62 ms |
3308 KB |
Output is correct |
6 |
Correct |
936 ms |
4332 KB |
Output is correct |
7 |
Correct |
811 ms |
4332 KB |
Output is correct |
8 |
Correct |
746 ms |
4204 KB |
Output is correct |
9 |
Correct |
683 ms |
4588 KB |
Output is correct |
10 |
Correct |
665 ms |
4572 KB |
Output is correct |
11 |
Correct |
676 ms |
4204 KB |
Output is correct |
12 |
Correct |
631 ms |
4204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1911 ms |
6264 KB |
Output is correct |
2 |
Correct |
62 ms |
3436 KB |
Output is correct |
3 |
Correct |
183 ms |
3820 KB |
Output is correct |
4 |
Correct |
108 ms |
3692 KB |
Output is correct |
5 |
Correct |
1371 ms |
6380 KB |
Output is correct |
6 |
Correct |
1955 ms |
6380 KB |
Output is correct |
7 |
Correct |
1375 ms |
6380 KB |
Output is correct |
8 |
Correct |
959 ms |
4844 KB |
Output is correct |
9 |
Correct |
999 ms |
4844 KB |
Output is correct |
10 |
Correct |
963 ms |
5228 KB |
Output is correct |
11 |
Correct |
1579 ms |
5564 KB |
Output is correct |
12 |
Correct |
1529 ms |
5612 KB |
Output is correct |
13 |
Correct |
1579 ms |
5740 KB |
Output is correct |
14 |
Correct |
1247 ms |
6380 KB |
Output is correct |
15 |
Correct |
1266 ms |
6508 KB |
Output is correct |
16 |
Correct |
2019 ms |
6260 KB |
Output is correct |
17 |
Correct |
2017 ms |
6248 KB |
Output is correct |
18 |
Correct |
2076 ms |
6380 KB |
Output is correct |
19 |
Correct |
2011 ms |
6248 KB |
Output is correct |
20 |
Correct |
1848 ms |
6012 KB |
Output is correct |
21 |
Correct |
1796 ms |
6012 KB |
Output is correct |
22 |
Correct |
1964 ms |
6280 KB |
Output is correct |
23 |
Correct |
1426 ms |
5996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1243 ms |
4716 KB |
Output is correct |
2 |
Correct |
1246 ms |
4724 KB |
Output is correct |
3 |
Correct |
1232 ms |
4740 KB |
Output is correct |
4 |
Correct |
1300 ms |
4844 KB |
Output is correct |
5 |
Correct |
1296 ms |
4716 KB |
Output is correct |
6 |
Correct |
1812 ms |
4972 KB |
Output is correct |
7 |
Correct |
1810 ms |
5100 KB |
Output is correct |
8 |
Correct |
1795 ms |
4972 KB |
Output is correct |
9 |
Correct |
62 ms |
3308 KB |
Output is correct |
10 |
Correct |
1325 ms |
4972 KB |
Output is correct |
11 |
Correct |
1234 ms |
4844 KB |
Output is correct |
12 |
Correct |
1225 ms |
5224 KB |
Output is correct |
13 |
Correct |
1200 ms |
4728 KB |
Output is correct |
14 |
Correct |
871 ms |
4204 KB |
Output is correct |
15 |
Correct |
522 ms |
3564 KB |
Output is correct |
16 |
Correct |
970 ms |
4332 KB |
Output is correct |
17 |
Correct |
865 ms |
4464 KB |
Output is correct |
18 |
Correct |
62 ms |
3308 KB |
Output is correct |
19 |
Correct |
936 ms |
4332 KB |
Output is correct |
20 |
Correct |
811 ms |
4332 KB |
Output is correct |
21 |
Correct |
746 ms |
4204 KB |
Output is correct |
22 |
Correct |
683 ms |
4588 KB |
Output is correct |
23 |
Correct |
665 ms |
4572 KB |
Output is correct |
24 |
Correct |
676 ms |
4204 KB |
Output is correct |
25 |
Correct |
631 ms |
4204 KB |
Output is correct |
26 |
Correct |
1241 ms |
4852 KB |
Output is correct |
27 |
Correct |
1484 ms |
4972 KB |
Output is correct |
28 |
Correct |
1355 ms |
4852 KB |
Output is correct |
29 |
Correct |
1122 ms |
4844 KB |
Output is correct |
30 |
Correct |
1514 ms |
5100 KB |
Output is correct |
31 |
Correct |
1505 ms |
4844 KB |
Output is correct |
32 |
Correct |
1511 ms |
4844 KB |
Output is correct |
33 |
Correct |
1331 ms |
4844 KB |
Output is correct |
34 |
Correct |
1338 ms |
4844 KB |
Output is correct |
35 |
Correct |
1361 ms |
4716 KB |
Output is correct |
36 |
Correct |
1148 ms |
4844 KB |
Output is correct |
37 |
Correct |
1154 ms |
4972 KB |
Output is correct |
38 |
Correct |
1138 ms |
4716 KB |
Output is correct |
39 |
Correct |
1049 ms |
4844 KB |
Output is correct |
40 |
Correct |
1051 ms |
4844 KB |
Output is correct |
41 |
Correct |
1040 ms |
4844 KB |
Output is correct |
42 |
Correct |
974 ms |
4716 KB |
Output is correct |
43 |
Correct |
976 ms |
4716 KB |
Output is correct |
44 |
Correct |
966 ms |
4716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1132 KB |
Output is correct |
2 |
Correct |
1 ms |
1132 KB |
Output is correct |
3 |
Correct |
19 ms |
1388 KB |
Output is correct |
4 |
Correct |
7 ms |
1388 KB |
Output is correct |
5 |
Correct |
14 ms |
1388 KB |
Output is correct |
6 |
Correct |
11 ms |
1388 KB |
Output is correct |
7 |
Correct |
13 ms |
1388 KB |
Output is correct |
8 |
Correct |
15 ms |
1388 KB |
Output is correct |
9 |
Correct |
15 ms |
1388 KB |
Output is correct |
10 |
Correct |
15 ms |
1388 KB |
Output is correct |
11 |
Correct |
14 ms |
1388 KB |
Output is correct |
12 |
Correct |
18 ms |
1516 KB |
Output is correct |
13 |
Correct |
19 ms |
1388 KB |
Output is correct |
14 |
Correct |
18 ms |
1408 KB |
Output is correct |
15 |
Correct |
16 ms |
1388 KB |
Output is correct |
16 |
Correct |
15 ms |
1516 KB |
Output is correct |
17 |
Correct |
15 ms |
1388 KB |
Output is correct |
18 |
Correct |
1243 ms |
4716 KB |
Output is correct |
19 |
Correct |
1246 ms |
4724 KB |
Output is correct |
20 |
Correct |
1232 ms |
4740 KB |
Output is correct |
21 |
Correct |
1300 ms |
4844 KB |
Output is correct |
22 |
Correct |
1296 ms |
4716 KB |
Output is correct |
23 |
Correct |
1812 ms |
4972 KB |
Output is correct |
24 |
Correct |
1810 ms |
5100 KB |
Output is correct |
25 |
Correct |
1795 ms |
4972 KB |
Output is correct |
26 |
Correct |
62 ms |
3308 KB |
Output is correct |
27 |
Correct |
1325 ms |
4972 KB |
Output is correct |
28 |
Correct |
1234 ms |
4844 KB |
Output is correct |
29 |
Correct |
1225 ms |
5224 KB |
Output is correct |
30 |
Correct |
1200 ms |
4728 KB |
Output is correct |
31 |
Correct |
871 ms |
4204 KB |
Output is correct |
32 |
Correct |
522 ms |
3564 KB |
Output is correct |
33 |
Correct |
970 ms |
4332 KB |
Output is correct |
34 |
Correct |
865 ms |
4464 KB |
Output is correct |
35 |
Correct |
62 ms |
3308 KB |
Output is correct |
36 |
Correct |
936 ms |
4332 KB |
Output is correct |
37 |
Correct |
811 ms |
4332 KB |
Output is correct |
38 |
Correct |
746 ms |
4204 KB |
Output is correct |
39 |
Correct |
683 ms |
4588 KB |
Output is correct |
40 |
Correct |
665 ms |
4572 KB |
Output is correct |
41 |
Correct |
676 ms |
4204 KB |
Output is correct |
42 |
Correct |
631 ms |
4204 KB |
Output is correct |
43 |
Correct |
1911 ms |
6264 KB |
Output is correct |
44 |
Correct |
62 ms |
3436 KB |
Output is correct |
45 |
Correct |
183 ms |
3820 KB |
Output is correct |
46 |
Correct |
108 ms |
3692 KB |
Output is correct |
47 |
Correct |
1371 ms |
6380 KB |
Output is correct |
48 |
Correct |
1955 ms |
6380 KB |
Output is correct |
49 |
Correct |
1375 ms |
6380 KB |
Output is correct |
50 |
Correct |
959 ms |
4844 KB |
Output is correct |
51 |
Correct |
999 ms |
4844 KB |
Output is correct |
52 |
Correct |
963 ms |
5228 KB |
Output is correct |
53 |
Correct |
1579 ms |
5564 KB |
Output is correct |
54 |
Correct |
1529 ms |
5612 KB |
Output is correct |
55 |
Correct |
1579 ms |
5740 KB |
Output is correct |
56 |
Correct |
1247 ms |
6380 KB |
Output is correct |
57 |
Correct |
1266 ms |
6508 KB |
Output is correct |
58 |
Correct |
2019 ms |
6260 KB |
Output is correct |
59 |
Correct |
2017 ms |
6248 KB |
Output is correct |
60 |
Correct |
2076 ms |
6380 KB |
Output is correct |
61 |
Correct |
2011 ms |
6248 KB |
Output is correct |
62 |
Correct |
1848 ms |
6012 KB |
Output is correct |
63 |
Correct |
1796 ms |
6012 KB |
Output is correct |
64 |
Correct |
1964 ms |
6280 KB |
Output is correct |
65 |
Correct |
1426 ms |
5996 KB |
Output is correct |
66 |
Correct |
1241 ms |
4852 KB |
Output is correct |
67 |
Correct |
1484 ms |
4972 KB |
Output is correct |
68 |
Correct |
1355 ms |
4852 KB |
Output is correct |
69 |
Correct |
1122 ms |
4844 KB |
Output is correct |
70 |
Correct |
1514 ms |
5100 KB |
Output is correct |
71 |
Correct |
1505 ms |
4844 KB |
Output is correct |
72 |
Correct |
1511 ms |
4844 KB |
Output is correct |
73 |
Correct |
1331 ms |
4844 KB |
Output is correct |
74 |
Correct |
1338 ms |
4844 KB |
Output is correct |
75 |
Correct |
1361 ms |
4716 KB |
Output is correct |
76 |
Correct |
1148 ms |
4844 KB |
Output is correct |
77 |
Correct |
1154 ms |
4972 KB |
Output is correct |
78 |
Correct |
1138 ms |
4716 KB |
Output is correct |
79 |
Correct |
1049 ms |
4844 KB |
Output is correct |
80 |
Correct |
1051 ms |
4844 KB |
Output is correct |
81 |
Correct |
1040 ms |
4844 KB |
Output is correct |
82 |
Correct |
974 ms |
4716 KB |
Output is correct |
83 |
Correct |
976 ms |
4716 KB |
Output is correct |
84 |
Correct |
966 ms |
4716 KB |
Output is correct |
85 |
Correct |
2214 ms |
6012 KB |
Output is correct |
86 |
Correct |
202 ms |
5740 KB |
Output is correct |
87 |
Correct |
134 ms |
5868 KB |
Output is correct |
88 |
Correct |
1918 ms |
8576 KB |
Output is correct |
89 |
Correct |
2217 ms |
9964 KB |
Output is correct |
90 |
Correct |
1843 ms |
8556 KB |
Output is correct |
91 |
Correct |
1395 ms |
7404 KB |
Output is correct |
92 |
Correct |
1361 ms |
7660 KB |
Output is correct |
93 |
Correct |
1836 ms |
7532 KB |
Output is correct |
94 |
Correct |
1943 ms |
8684 KB |
Output is correct |
95 |
Correct |
1952 ms |
8772 KB |
Output is correct |
96 |
Correct |
2075 ms |
8872 KB |
Output is correct |
97 |
Correct |
1612 ms |
8684 KB |
Output is correct |
98 |
Correct |
1710 ms |
8300 KB |
Output is correct |
99 |
Correct |
2331 ms |
9836 KB |
Output is correct |
100 |
Correct |
2364 ms |
9836 KB |
Output is correct |
101 |
Correct |
2348 ms |
9860 KB |
Output is correct |
102 |
Correct |
2382 ms |
9844 KB |
Output is correct |
103 |
Correct |
2284 ms |
9068 KB |
Output is correct |
104 |
Correct |
2290 ms |
9068 KB |
Output is correct |
105 |
Correct |
1969 ms |
8940 KB |
Output is correct |
106 |
Correct |
1684 ms |
8556 KB |
Output is correct |
107 |
Correct |
2027 ms |
9244 KB |
Output is correct |
108 |
Correct |
2325 ms |
9708 KB |
Output is correct |
109 |
Correct |
1840 ms |
7788 KB |
Output is correct |