#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b){a = b; return true;}
return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b){a = b; return true;}
return false;
}
template <class T>
void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
for(auto i: a) out << i << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
struct DSU{
int n;
vector<int> parent, sz;
bool flag;
vector<pair<int, int>> history;
DSU(int _n){
n = _n;
parent.resize(n+1); sz.resize(n+1, 1);
for(int i= 1; i<=n; ++i) parent[i] = i;
flag = 0;
}
int find_set(int u){
if (u == parent[u]) return u;
if (flag) return find_set(parent[u]);
else return parent[u] = find_set(parent[u]);
}
bool same_set(int u, int v){return find_set(u) == find_set(v);}
bool join_set(int u, int v){
u = find_set(u), v = find_set(v);
if (u != v){
if (sz[u] < sz[v]) swap(u, v);
parent[v] = u;
sz[u] += sz[v];
if (flag) history.push_back({u, v});
return true;
}
return false;
}
int get_size(int u){return sz[find_set(u)];}
void toggle(){flag = !flag;}
int get_version(){return history.size();}
void roll_back(int version){
while(history.size() > version){
int u = history.back().first, v = history.back().second;
history.pop_back();
parent[v] = v;
sz[u] -= sz[v];
}
}
};
const int N = 1e5 + 69;
const int BLOCK = 350;
int n, m;
array<int, 3> edge[N];
array<int, 3> queries[N];
bool check[N];
vector<array<int, 3>> sweep[N * 2];
int ans[N];
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
for(int i = 1; i<=m; ++i) cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
int q; cin >> q;
for(int i = 1; i<=q; ++i){
cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
}
vector<int> b;
for(int i= 1; i<=m; ++i) b.push_back(edge[i][2]);
for(int i= 1; i<=q; ++i) b.push_back(queries[i][2]);
remove_dup(b);
for(int i = 1; i<=m; ++i) edge[i][2] = lower_bound(ALL(b), edge[i][2]) - b.begin();
for(int i = 1; i<=q; ++i) queries[i][2]= lower_bound(ALL(b), queries[i][2]) - b.begin();
for(int t= 1; t <= q; t += BLOCK){
int l = t, r = min(t + BLOCK - 1, q);
vector<int> ligma;
for(int i= l; i<=r; ++i){
if (queries[i][0] == 1 && !check[queries[i][1]]){
check[queries[i][1]] = true;
ligma.push_back(queries[i][1]);
}
}
DSU mst(n);
for(int i = b.size(); i>=0; --i) sweep[i].clear();
for(int i = 1; i<=m; ++i) if (!check[i]){
sweep[edge[i][2]].push_back({{0,edge[i][0], edge[i][1]}});
}
for(int i = l; i<=r; ++i) if (queries[i][0] == 2){
sweep[queries[i][2]].push_back({{i,queries[i][1], queries[i][2]}});
}
for(int i = b.size(); i>=0; --i){
for(array<int, 3> j: sweep[i]){
if (j[0] == 0){
mst.join_set(j[1], j[2]);
}
else{
for(int k: ligma) mst.same_set(edge[k][0], edge[k][1]);
mst.toggle();
int cur = mst.get_version();
for(int k = l; k <= j[0]; ++k){
if (queries[k][0] == 1){
int e = queries[k][1];
swap(edge[e][2], queries[k][2]);
}
}
for(int k: ligma) {
if (edge[k][2] >= i) mst.join_set(edge[k][0], edge[k][1]);
}
ans[j[0]] = mst.get_size(j[1]);
mst.roll_back(cur);
mst.toggle();
for(int k = j[0]; k >= l; --k){
if (queries[k][0] == 1){
int e = queries[k][1];
swap(edge[e][2], queries[k][2]);
}
}
}
}
}
for(int i= l; i<=r; ++i){
if (queries[i][0] == 1){
int e = queries[i][1];
check[e] = false;
edge[e][2] = queries[i][2];
}
}
}
for(int i = 1; i<=q; ++i) if (queries[i][0] == 2) cout << ans[i] << "\n";
return 0;
}
Compilation message
bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:83:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
83 | while(history.size() > version){
| ~~~~~~~~~~~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
17 ms |
7004 KB |
Output is correct |
4 |
Correct |
8 ms |
7000 KB |
Output is correct |
5 |
Correct |
13 ms |
6940 KB |
Output is correct |
6 |
Correct |
11 ms |
6748 KB |
Output is correct |
7 |
Correct |
11 ms |
6744 KB |
Output is correct |
8 |
Correct |
14 ms |
6976 KB |
Output is correct |
9 |
Correct |
12 ms |
7076 KB |
Output is correct |
10 |
Correct |
14 ms |
7000 KB |
Output is correct |
11 |
Correct |
15 ms |
7000 KB |
Output is correct |
12 |
Correct |
14 ms |
7004 KB |
Output is correct |
13 |
Correct |
15 ms |
7000 KB |
Output is correct |
14 |
Correct |
17 ms |
7000 KB |
Output is correct |
15 |
Correct |
15 ms |
7004 KB |
Output is correct |
16 |
Correct |
14 ms |
6748 KB |
Output is correct |
17 |
Correct |
11 ms |
6636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1145 ms |
14612 KB |
Output is correct |
2 |
Correct |
1143 ms |
15876 KB |
Output is correct |
3 |
Correct |
1073 ms |
15724 KB |
Output is correct |
4 |
Correct |
1079 ms |
15848 KB |
Output is correct |
5 |
Correct |
1109 ms |
15880 KB |
Output is correct |
6 |
Correct |
1060 ms |
15120 KB |
Output is correct |
7 |
Correct |
1090 ms |
15304 KB |
Output is correct |
8 |
Correct |
1111 ms |
15512 KB |
Output is correct |
9 |
Correct |
184 ms |
11728 KB |
Output is correct |
10 |
Correct |
443 ms |
11092 KB |
Output is correct |
11 |
Correct |
368 ms |
11284 KB |
Output is correct |
12 |
Correct |
787 ms |
15412 KB |
Output is correct |
13 |
Correct |
1010 ms |
15676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
736 ms |
13576 KB |
Output is correct |
2 |
Correct |
346 ms |
11704 KB |
Output is correct |
3 |
Correct |
740 ms |
13440 KB |
Output is correct |
4 |
Correct |
705 ms |
14664 KB |
Output is correct |
5 |
Correct |
152 ms |
11692 KB |
Output is correct |
6 |
Correct |
734 ms |
14412 KB |
Output is correct |
7 |
Correct |
712 ms |
14392 KB |
Output is correct |
8 |
Correct |
724 ms |
14536 KB |
Output is correct |
9 |
Correct |
651 ms |
14576 KB |
Output is correct |
10 |
Correct |
656 ms |
14600 KB |
Output is correct |
11 |
Correct |
621 ms |
14180 KB |
Output is correct |
12 |
Correct |
603 ms |
14288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1620 ms |
17840 KB |
Output is correct |
2 |
Correct |
155 ms |
11424 KB |
Output is correct |
3 |
Correct |
111 ms |
13304 KB |
Output is correct |
4 |
Correct |
63 ms |
11416 KB |
Output is correct |
5 |
Correct |
724 ms |
12684 KB |
Output is correct |
6 |
Correct |
1618 ms |
17668 KB |
Output is correct |
7 |
Correct |
737 ms |
12848 KB |
Output is correct |
8 |
Correct |
957 ms |
14704 KB |
Output is correct |
9 |
Correct |
1002 ms |
14780 KB |
Output is correct |
10 |
Correct |
723 ms |
14676 KB |
Output is correct |
11 |
Correct |
1444 ms |
16144 KB |
Output is correct |
12 |
Correct |
1449 ms |
16252 KB |
Output is correct |
13 |
Correct |
999 ms |
16268 KB |
Output is correct |
14 |
Correct |
610 ms |
12652 KB |
Output is correct |
15 |
Correct |
755 ms |
12664 KB |
Output is correct |
16 |
Correct |
1840 ms |
17856 KB |
Output is correct |
17 |
Correct |
1904 ms |
17720 KB |
Output is correct |
18 |
Correct |
1759 ms |
17856 KB |
Output is correct |
19 |
Correct |
1755 ms |
17812 KB |
Output is correct |
20 |
Correct |
1223 ms |
16668 KB |
Output is correct |
21 |
Correct |
1196 ms |
16776 KB |
Output is correct |
22 |
Correct |
1453 ms |
17824 KB |
Output is correct |
23 |
Correct |
772 ms |
12020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1145 ms |
14612 KB |
Output is correct |
2 |
Correct |
1143 ms |
15876 KB |
Output is correct |
3 |
Correct |
1073 ms |
15724 KB |
Output is correct |
4 |
Correct |
1079 ms |
15848 KB |
Output is correct |
5 |
Correct |
1109 ms |
15880 KB |
Output is correct |
6 |
Correct |
1060 ms |
15120 KB |
Output is correct |
7 |
Correct |
1090 ms |
15304 KB |
Output is correct |
8 |
Correct |
1111 ms |
15512 KB |
Output is correct |
9 |
Correct |
184 ms |
11728 KB |
Output is correct |
10 |
Correct |
443 ms |
11092 KB |
Output is correct |
11 |
Correct |
368 ms |
11284 KB |
Output is correct |
12 |
Correct |
787 ms |
15412 KB |
Output is correct |
13 |
Correct |
1010 ms |
15676 KB |
Output is correct |
14 |
Correct |
736 ms |
13576 KB |
Output is correct |
15 |
Correct |
346 ms |
11704 KB |
Output is correct |
16 |
Correct |
740 ms |
13440 KB |
Output is correct |
17 |
Correct |
705 ms |
14664 KB |
Output is correct |
18 |
Correct |
152 ms |
11692 KB |
Output is correct |
19 |
Correct |
734 ms |
14412 KB |
Output is correct |
20 |
Correct |
712 ms |
14392 KB |
Output is correct |
21 |
Correct |
724 ms |
14536 KB |
Output is correct |
22 |
Correct |
651 ms |
14576 KB |
Output is correct |
23 |
Correct |
656 ms |
14600 KB |
Output is correct |
24 |
Correct |
621 ms |
14180 KB |
Output is correct |
25 |
Correct |
603 ms |
14288 KB |
Output is correct |
26 |
Correct |
1093 ms |
15820 KB |
Output is correct |
27 |
Correct |
1228 ms |
15052 KB |
Output is correct |
28 |
Correct |
1160 ms |
15748 KB |
Output is correct |
29 |
Correct |
1066 ms |
15768 KB |
Output is correct |
30 |
Correct |
1103 ms |
15344 KB |
Output is correct |
31 |
Correct |
1176 ms |
15212 KB |
Output is correct |
32 |
Correct |
1142 ms |
15372 KB |
Output is correct |
33 |
Correct |
1109 ms |
15824 KB |
Output is correct |
34 |
Correct |
1168 ms |
15820 KB |
Output is correct |
35 |
Correct |
1134 ms |
16000 KB |
Output is correct |
36 |
Correct |
1103 ms |
15776 KB |
Output is correct |
37 |
Correct |
1069 ms |
15800 KB |
Output is correct |
38 |
Correct |
1072 ms |
15676 KB |
Output is correct |
39 |
Correct |
962 ms |
15912 KB |
Output is correct |
40 |
Correct |
972 ms |
16228 KB |
Output is correct |
41 |
Correct |
1020 ms |
15864 KB |
Output is correct |
42 |
Correct |
987 ms |
15636 KB |
Output is correct |
43 |
Correct |
1014 ms |
15748 KB |
Output is correct |
44 |
Correct |
1046 ms |
15844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
17 ms |
7004 KB |
Output is correct |
4 |
Correct |
8 ms |
7000 KB |
Output is correct |
5 |
Correct |
13 ms |
6940 KB |
Output is correct |
6 |
Correct |
11 ms |
6748 KB |
Output is correct |
7 |
Correct |
11 ms |
6744 KB |
Output is correct |
8 |
Correct |
14 ms |
6976 KB |
Output is correct |
9 |
Correct |
12 ms |
7076 KB |
Output is correct |
10 |
Correct |
14 ms |
7000 KB |
Output is correct |
11 |
Correct |
15 ms |
7000 KB |
Output is correct |
12 |
Correct |
14 ms |
7004 KB |
Output is correct |
13 |
Correct |
15 ms |
7000 KB |
Output is correct |
14 |
Correct |
17 ms |
7000 KB |
Output is correct |
15 |
Correct |
15 ms |
7004 KB |
Output is correct |
16 |
Correct |
14 ms |
6748 KB |
Output is correct |
17 |
Correct |
11 ms |
6636 KB |
Output is correct |
18 |
Correct |
1145 ms |
14612 KB |
Output is correct |
19 |
Correct |
1143 ms |
15876 KB |
Output is correct |
20 |
Correct |
1073 ms |
15724 KB |
Output is correct |
21 |
Correct |
1079 ms |
15848 KB |
Output is correct |
22 |
Correct |
1109 ms |
15880 KB |
Output is correct |
23 |
Correct |
1060 ms |
15120 KB |
Output is correct |
24 |
Correct |
1090 ms |
15304 KB |
Output is correct |
25 |
Correct |
1111 ms |
15512 KB |
Output is correct |
26 |
Correct |
184 ms |
11728 KB |
Output is correct |
27 |
Correct |
443 ms |
11092 KB |
Output is correct |
28 |
Correct |
368 ms |
11284 KB |
Output is correct |
29 |
Correct |
787 ms |
15412 KB |
Output is correct |
30 |
Correct |
1010 ms |
15676 KB |
Output is correct |
31 |
Correct |
736 ms |
13576 KB |
Output is correct |
32 |
Correct |
346 ms |
11704 KB |
Output is correct |
33 |
Correct |
740 ms |
13440 KB |
Output is correct |
34 |
Correct |
705 ms |
14664 KB |
Output is correct |
35 |
Correct |
152 ms |
11692 KB |
Output is correct |
36 |
Correct |
734 ms |
14412 KB |
Output is correct |
37 |
Correct |
712 ms |
14392 KB |
Output is correct |
38 |
Correct |
724 ms |
14536 KB |
Output is correct |
39 |
Correct |
651 ms |
14576 KB |
Output is correct |
40 |
Correct |
656 ms |
14600 KB |
Output is correct |
41 |
Correct |
621 ms |
14180 KB |
Output is correct |
42 |
Correct |
603 ms |
14288 KB |
Output is correct |
43 |
Correct |
1620 ms |
17840 KB |
Output is correct |
44 |
Correct |
155 ms |
11424 KB |
Output is correct |
45 |
Correct |
111 ms |
13304 KB |
Output is correct |
46 |
Correct |
63 ms |
11416 KB |
Output is correct |
47 |
Correct |
724 ms |
12684 KB |
Output is correct |
48 |
Correct |
1618 ms |
17668 KB |
Output is correct |
49 |
Correct |
737 ms |
12848 KB |
Output is correct |
50 |
Correct |
957 ms |
14704 KB |
Output is correct |
51 |
Correct |
1002 ms |
14780 KB |
Output is correct |
52 |
Correct |
723 ms |
14676 KB |
Output is correct |
53 |
Correct |
1444 ms |
16144 KB |
Output is correct |
54 |
Correct |
1449 ms |
16252 KB |
Output is correct |
55 |
Correct |
999 ms |
16268 KB |
Output is correct |
56 |
Correct |
610 ms |
12652 KB |
Output is correct |
57 |
Correct |
755 ms |
12664 KB |
Output is correct |
58 |
Correct |
1840 ms |
17856 KB |
Output is correct |
59 |
Correct |
1904 ms |
17720 KB |
Output is correct |
60 |
Correct |
1759 ms |
17856 KB |
Output is correct |
61 |
Correct |
1755 ms |
17812 KB |
Output is correct |
62 |
Correct |
1223 ms |
16668 KB |
Output is correct |
63 |
Correct |
1196 ms |
16776 KB |
Output is correct |
64 |
Correct |
1453 ms |
17824 KB |
Output is correct |
65 |
Correct |
772 ms |
12020 KB |
Output is correct |
66 |
Correct |
1093 ms |
15820 KB |
Output is correct |
67 |
Correct |
1228 ms |
15052 KB |
Output is correct |
68 |
Correct |
1160 ms |
15748 KB |
Output is correct |
69 |
Correct |
1066 ms |
15768 KB |
Output is correct |
70 |
Correct |
1103 ms |
15344 KB |
Output is correct |
71 |
Correct |
1176 ms |
15212 KB |
Output is correct |
72 |
Correct |
1142 ms |
15372 KB |
Output is correct |
73 |
Correct |
1109 ms |
15824 KB |
Output is correct |
74 |
Correct |
1168 ms |
15820 KB |
Output is correct |
75 |
Correct |
1134 ms |
16000 KB |
Output is correct |
76 |
Correct |
1103 ms |
15776 KB |
Output is correct |
77 |
Correct |
1069 ms |
15800 KB |
Output is correct |
78 |
Correct |
1072 ms |
15676 KB |
Output is correct |
79 |
Correct |
962 ms |
15912 KB |
Output is correct |
80 |
Correct |
972 ms |
16228 KB |
Output is correct |
81 |
Correct |
1020 ms |
15864 KB |
Output is correct |
82 |
Correct |
987 ms |
15636 KB |
Output is correct |
83 |
Correct |
1014 ms |
15748 KB |
Output is correct |
84 |
Correct |
1046 ms |
15844 KB |
Output is correct |
85 |
Correct |
1877 ms |
19248 KB |
Output is correct |
86 |
Correct |
114 ms |
13780 KB |
Output is correct |
87 |
Correct |
75 ms |
12236 KB |
Output is correct |
88 |
Correct |
882 ms |
13432 KB |
Output is correct |
89 |
Correct |
1888 ms |
19324 KB |
Output is correct |
90 |
Correct |
880 ms |
13680 KB |
Output is correct |
91 |
Correct |
1156 ms |
15704 KB |
Output is correct |
92 |
Correct |
1217 ms |
15796 KB |
Output is correct |
93 |
Correct |
1165 ms |
15844 KB |
Output is correct |
94 |
Correct |
1670 ms |
17368 KB |
Output is correct |
95 |
Correct |
1615 ms |
17452 KB |
Output is correct |
96 |
Correct |
1410 ms |
17536 KB |
Output is correct |
97 |
Correct |
764 ms |
13892 KB |
Output is correct |
98 |
Correct |
775 ms |
13500 KB |
Output is correct |
99 |
Correct |
1923 ms |
19316 KB |
Output is correct |
100 |
Correct |
1981 ms |
19228 KB |
Output is correct |
101 |
Correct |
1950 ms |
19416 KB |
Output is correct |
102 |
Correct |
1905 ms |
19228 KB |
Output is correct |
103 |
Correct |
1519 ms |
17980 KB |
Output is correct |
104 |
Correct |
1516 ms |
18212 KB |
Output is correct |
105 |
Correct |
1587 ms |
18036 KB |
Output is correct |
106 |
Correct |
1438 ms |
17360 KB |
Output is correct |
107 |
Correct |
1296 ms |
18404 KB |
Output is correct |
108 |
Correct |
1670 ms |
19144 KB |
Output is correct |
109 |
Correct |
716 ms |
12540 KB |
Output is correct |