#include <bits/stdc++.h>
using namespace std;
#define ms(x, a) memset(x, a, sizeof x)
typedef long long ll;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f;
const int MN = 5e4 + 1, MM = 1e5 + 1, MQ = 1e5 + 1;
const int SZ = 1000;
struct DisjointSet{
vector<int> p, sz;
vector<pair<int,int>> hist;
DisjointSet(int N){
p = vector<int>(N + 1);
sz = vector<int>(N + 1);
reset();
}
int Find(int x){ return p[x] == x ? x : Find(p[x]); }
void Union(int a, int b){
a = Find(a), b = Find(b);
if (a == b) a = -1, b = -1;
else{
if (sz[b] > sz[a]) swap(a, b);
p[b] = a, sz[a] += sz[b];
}
hist.push_back({a, b});
}
void undo(){
assert(!hist.empty());
auto [a, b] = hist.back(); hist.pop_back();
if (a == -1) return;
sz[a] -= sz[b], p[b] = b;
}
int getsz(int v){ return sz[Find(v)]; }
void reset(){
hist.clear();
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
};
struct Edge{ int a, b, w; } all_edges[MM];
struct Query{ int v, w, t; };
int changes[MM], ans[MQ];
int main(){
cin.tie(0)->sync_with_stdio(0);
int N, M; cin >> N >> M;
for (int i = 1; i <= M; ++i){
int a, b, w; cin >> a >> b >> w;
all_edges[i] = {a, b, w};
}
int Q; cin >> Q;
vector<Query> qs1, qs2;
DisjointSet dsu(N);
for (int _ = 1; _ <= Q; ++_){
int op, v, w; cin >> op >> v >> w;
if (op == 1) qs1.push_back({v, w, _}), all_edges[v].w = -abs(all_edges[v].w);
if (op == 2) qs2.push_back({v, w, _});
if ((Q - _) % SZ) continue;
vector<Edge> edges;
vector<int> look;
dsu.reset();
for (int i = 1; i <= M; ++i){
if (all_edges[i].w > 0) edges.push_back(all_edges[i]);
else look.push_back(i);
}
sort(edges.begin(), edges.end(), [](Edge a, Edge b){ return a.w > b.w; });
sort(qs2.begin(), qs2.end(), [](Query a, Query b){ return a.w > b.w; });
int pl = 0;
for (auto [v, w, t] : qs2){
while (pl != edges.size() && edges[pl].w >= w) dsu.Union(edges[pl].a, edges[pl].b), ++pl;
for (int i : look) changes[i] = -all_edges[i].w;
for (auto [ev, ew, et] : qs1){
if (et <= t) changes[ev] = ew;
else break;
}
int T = 0;
for (int i : look){
int ew = changes[i];
if (ew >= w){
dsu.Union(all_edges[i].a, all_edges[i].b);
++T;
}
}
ans[t] = dsu.getsz(v);
for (int i = 1; i <= T; ++i) dsu.undo();
}
for (auto [v, w, t] : qs1) all_edges[v].w = w;
for (int i = 1; i <= M; ++i) all_edges[i].w = abs(all_edges[i].w);
qs1.clear(), qs2.clear(); look.clear();
}
for (int i = 1; i <= Q; ++i){
if (ans[i]) cout << ans[i] << '\n';
}
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | while (pl != edges.size() && edges[pl].w >= w) dsu.Union(edges[pl].a, edges[pl].b), ++pl;
| ~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
40 ms |
432 KB |
Output is correct |
4 |
Correct |
5 ms |
332 KB |
Output is correct |
5 |
Correct |
16 ms |
408 KB |
Output is correct |
6 |
Correct |
14 ms |
380 KB |
Output is correct |
7 |
Correct |
16 ms |
380 KB |
Output is correct |
8 |
Correct |
16 ms |
392 KB |
Output is correct |
9 |
Correct |
18 ms |
332 KB |
Output is correct |
10 |
Correct |
16 ms |
416 KB |
Output is correct |
11 |
Correct |
16 ms |
396 KB |
Output is correct |
12 |
Correct |
18 ms |
364 KB |
Output is correct |
13 |
Correct |
22 ms |
368 KB |
Output is correct |
14 |
Correct |
21 ms |
332 KB |
Output is correct |
15 |
Correct |
18 ms |
400 KB |
Output is correct |
16 |
Correct |
16 ms |
332 KB |
Output is correct |
17 |
Correct |
16 ms |
392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1302 ms |
3668 KB |
Output is correct |
2 |
Correct |
1311 ms |
3872 KB |
Output is correct |
3 |
Correct |
1305 ms |
3832 KB |
Output is correct |
4 |
Correct |
1284 ms |
3616 KB |
Output is correct |
5 |
Correct |
1293 ms |
3868 KB |
Output is correct |
6 |
Correct |
1737 ms |
3780 KB |
Output is correct |
7 |
Correct |
1752 ms |
3856 KB |
Output is correct |
8 |
Correct |
1747 ms |
3860 KB |
Output is correct |
9 |
Correct |
41 ms |
832 KB |
Output is correct |
10 |
Correct |
1141 ms |
3652 KB |
Output is correct |
11 |
Correct |
1077 ms |
3824 KB |
Output is correct |
12 |
Correct |
1099 ms |
3684 KB |
Output is correct |
13 |
Correct |
1080 ms |
3868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1046 ms |
2560 KB |
Output is correct |
2 |
Correct |
760 ms |
1476 KB |
Output is correct |
3 |
Correct |
1196 ms |
2672 KB |
Output is correct |
4 |
Correct |
1035 ms |
2712 KB |
Output is correct |
5 |
Correct |
41 ms |
824 KB |
Output is correct |
6 |
Correct |
1137 ms |
2648 KB |
Output is correct |
7 |
Correct |
956 ms |
2612 KB |
Output is correct |
8 |
Correct |
882 ms |
2728 KB |
Output is correct |
9 |
Correct |
672 ms |
2668 KB |
Output is correct |
10 |
Correct |
617 ms |
2412 KB |
Output is correct |
11 |
Correct |
679 ms |
2616 KB |
Output is correct |
12 |
Correct |
617 ms |
2560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1434 ms |
6328 KB |
Output is correct |
2 |
Correct |
44 ms |
2292 KB |
Output is correct |
3 |
Correct |
161 ms |
6984 KB |
Output is correct |
4 |
Correct |
99 ms |
7020 KB |
Output is correct |
5 |
Correct |
931 ms |
8100 KB |
Output is correct |
6 |
Correct |
1401 ms |
9780 KB |
Output is correct |
7 |
Correct |
860 ms |
8264 KB |
Output is correct |
8 |
Correct |
684 ms |
6176 KB |
Output is correct |
9 |
Correct |
674 ms |
6260 KB |
Output is correct |
10 |
Correct |
694 ms |
6124 KB |
Output is correct |
11 |
Correct |
1108 ms |
8164 KB |
Output is correct |
12 |
Correct |
1062 ms |
8368 KB |
Output is correct |
13 |
Correct |
1109 ms |
8248 KB |
Output is correct |
14 |
Correct |
869 ms |
8152 KB |
Output is correct |
15 |
Correct |
868 ms |
8112 KB |
Output is correct |
16 |
Correct |
1439 ms |
9744 KB |
Output is correct |
17 |
Correct |
1471 ms |
9620 KB |
Output is correct |
18 |
Correct |
1437 ms |
9772 KB |
Output is correct |
19 |
Correct |
1466 ms |
9744 KB |
Output is correct |
20 |
Correct |
1213 ms |
8548 KB |
Output is correct |
21 |
Correct |
1226 ms |
8492 KB |
Output is correct |
22 |
Correct |
1386 ms |
9232 KB |
Output is correct |
23 |
Correct |
878 ms |
7260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1302 ms |
3668 KB |
Output is correct |
2 |
Correct |
1311 ms |
3872 KB |
Output is correct |
3 |
Correct |
1305 ms |
3832 KB |
Output is correct |
4 |
Correct |
1284 ms |
3616 KB |
Output is correct |
5 |
Correct |
1293 ms |
3868 KB |
Output is correct |
6 |
Correct |
1737 ms |
3780 KB |
Output is correct |
7 |
Correct |
1752 ms |
3856 KB |
Output is correct |
8 |
Correct |
1747 ms |
3860 KB |
Output is correct |
9 |
Correct |
41 ms |
832 KB |
Output is correct |
10 |
Correct |
1141 ms |
3652 KB |
Output is correct |
11 |
Correct |
1077 ms |
3824 KB |
Output is correct |
12 |
Correct |
1099 ms |
3684 KB |
Output is correct |
13 |
Correct |
1080 ms |
3868 KB |
Output is correct |
14 |
Correct |
1046 ms |
2560 KB |
Output is correct |
15 |
Correct |
760 ms |
1476 KB |
Output is correct |
16 |
Correct |
1196 ms |
2672 KB |
Output is correct |
17 |
Correct |
1035 ms |
2712 KB |
Output is correct |
18 |
Correct |
41 ms |
824 KB |
Output is correct |
19 |
Correct |
1137 ms |
2648 KB |
Output is correct |
20 |
Correct |
956 ms |
2612 KB |
Output is correct |
21 |
Correct |
882 ms |
2728 KB |
Output is correct |
22 |
Correct |
672 ms |
2668 KB |
Output is correct |
23 |
Correct |
617 ms |
2412 KB |
Output is correct |
24 |
Correct |
679 ms |
2616 KB |
Output is correct |
25 |
Correct |
617 ms |
2560 KB |
Output is correct |
26 |
Correct |
1325 ms |
3612 KB |
Output is correct |
27 |
Correct |
1662 ms |
3652 KB |
Output is correct |
28 |
Correct |
1393 ms |
3784 KB |
Output is correct |
29 |
Correct |
1073 ms |
3752 KB |
Output is correct |
30 |
Correct |
1592 ms |
3688 KB |
Output is correct |
31 |
Correct |
1621 ms |
3716 KB |
Output is correct |
32 |
Correct |
1629 ms |
3740 KB |
Output is correct |
33 |
Correct |
1402 ms |
3660 KB |
Output is correct |
34 |
Correct |
1414 ms |
3764 KB |
Output is correct |
35 |
Correct |
1429 ms |
3692 KB |
Output is correct |
36 |
Correct |
1094 ms |
3632 KB |
Output is correct |
37 |
Correct |
1095 ms |
3624 KB |
Output is correct |
38 |
Correct |
1081 ms |
3660 KB |
Output is correct |
39 |
Correct |
821 ms |
3676 KB |
Output is correct |
40 |
Correct |
824 ms |
3756 KB |
Output is correct |
41 |
Correct |
824 ms |
3636 KB |
Output is correct |
42 |
Correct |
828 ms |
3628 KB |
Output is correct |
43 |
Correct |
829 ms |
3640 KB |
Output is correct |
44 |
Correct |
846 ms |
3648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
40 ms |
432 KB |
Output is correct |
4 |
Correct |
5 ms |
332 KB |
Output is correct |
5 |
Correct |
16 ms |
408 KB |
Output is correct |
6 |
Correct |
14 ms |
380 KB |
Output is correct |
7 |
Correct |
16 ms |
380 KB |
Output is correct |
8 |
Correct |
16 ms |
392 KB |
Output is correct |
9 |
Correct |
18 ms |
332 KB |
Output is correct |
10 |
Correct |
16 ms |
416 KB |
Output is correct |
11 |
Correct |
16 ms |
396 KB |
Output is correct |
12 |
Correct |
18 ms |
364 KB |
Output is correct |
13 |
Correct |
22 ms |
368 KB |
Output is correct |
14 |
Correct |
21 ms |
332 KB |
Output is correct |
15 |
Correct |
18 ms |
400 KB |
Output is correct |
16 |
Correct |
16 ms |
332 KB |
Output is correct |
17 |
Correct |
16 ms |
392 KB |
Output is correct |
18 |
Correct |
1302 ms |
3668 KB |
Output is correct |
19 |
Correct |
1311 ms |
3872 KB |
Output is correct |
20 |
Correct |
1305 ms |
3832 KB |
Output is correct |
21 |
Correct |
1284 ms |
3616 KB |
Output is correct |
22 |
Correct |
1293 ms |
3868 KB |
Output is correct |
23 |
Correct |
1737 ms |
3780 KB |
Output is correct |
24 |
Correct |
1752 ms |
3856 KB |
Output is correct |
25 |
Correct |
1747 ms |
3860 KB |
Output is correct |
26 |
Correct |
41 ms |
832 KB |
Output is correct |
27 |
Correct |
1141 ms |
3652 KB |
Output is correct |
28 |
Correct |
1077 ms |
3824 KB |
Output is correct |
29 |
Correct |
1099 ms |
3684 KB |
Output is correct |
30 |
Correct |
1080 ms |
3868 KB |
Output is correct |
31 |
Correct |
1046 ms |
2560 KB |
Output is correct |
32 |
Correct |
760 ms |
1476 KB |
Output is correct |
33 |
Correct |
1196 ms |
2672 KB |
Output is correct |
34 |
Correct |
1035 ms |
2712 KB |
Output is correct |
35 |
Correct |
41 ms |
824 KB |
Output is correct |
36 |
Correct |
1137 ms |
2648 KB |
Output is correct |
37 |
Correct |
956 ms |
2612 KB |
Output is correct |
38 |
Correct |
882 ms |
2728 KB |
Output is correct |
39 |
Correct |
672 ms |
2668 KB |
Output is correct |
40 |
Correct |
617 ms |
2412 KB |
Output is correct |
41 |
Correct |
679 ms |
2616 KB |
Output is correct |
42 |
Correct |
617 ms |
2560 KB |
Output is correct |
43 |
Correct |
1434 ms |
6328 KB |
Output is correct |
44 |
Correct |
44 ms |
2292 KB |
Output is correct |
45 |
Correct |
161 ms |
6984 KB |
Output is correct |
46 |
Correct |
99 ms |
7020 KB |
Output is correct |
47 |
Correct |
931 ms |
8100 KB |
Output is correct |
48 |
Correct |
1401 ms |
9780 KB |
Output is correct |
49 |
Correct |
860 ms |
8264 KB |
Output is correct |
50 |
Correct |
684 ms |
6176 KB |
Output is correct |
51 |
Correct |
674 ms |
6260 KB |
Output is correct |
52 |
Correct |
694 ms |
6124 KB |
Output is correct |
53 |
Correct |
1108 ms |
8164 KB |
Output is correct |
54 |
Correct |
1062 ms |
8368 KB |
Output is correct |
55 |
Correct |
1109 ms |
8248 KB |
Output is correct |
56 |
Correct |
869 ms |
8152 KB |
Output is correct |
57 |
Correct |
868 ms |
8112 KB |
Output is correct |
58 |
Correct |
1439 ms |
9744 KB |
Output is correct |
59 |
Correct |
1471 ms |
9620 KB |
Output is correct |
60 |
Correct |
1437 ms |
9772 KB |
Output is correct |
61 |
Correct |
1466 ms |
9744 KB |
Output is correct |
62 |
Correct |
1213 ms |
8548 KB |
Output is correct |
63 |
Correct |
1226 ms |
8492 KB |
Output is correct |
64 |
Correct |
1386 ms |
9232 KB |
Output is correct |
65 |
Correct |
878 ms |
7260 KB |
Output is correct |
66 |
Correct |
1325 ms |
3612 KB |
Output is correct |
67 |
Correct |
1662 ms |
3652 KB |
Output is correct |
68 |
Correct |
1393 ms |
3784 KB |
Output is correct |
69 |
Correct |
1073 ms |
3752 KB |
Output is correct |
70 |
Correct |
1592 ms |
3688 KB |
Output is correct |
71 |
Correct |
1621 ms |
3716 KB |
Output is correct |
72 |
Correct |
1629 ms |
3740 KB |
Output is correct |
73 |
Correct |
1402 ms |
3660 KB |
Output is correct |
74 |
Correct |
1414 ms |
3764 KB |
Output is correct |
75 |
Correct |
1429 ms |
3692 KB |
Output is correct |
76 |
Correct |
1094 ms |
3632 KB |
Output is correct |
77 |
Correct |
1095 ms |
3624 KB |
Output is correct |
78 |
Correct |
1081 ms |
3660 KB |
Output is correct |
79 |
Correct |
821 ms |
3676 KB |
Output is correct |
80 |
Correct |
824 ms |
3756 KB |
Output is correct |
81 |
Correct |
824 ms |
3636 KB |
Output is correct |
82 |
Correct |
828 ms |
3628 KB |
Output is correct |
83 |
Correct |
829 ms |
3640 KB |
Output is correct |
84 |
Correct |
846 ms |
3648 KB |
Output is correct |
85 |
Correct |
2053 ms |
10244 KB |
Output is correct |
86 |
Correct |
205 ms |
7292 KB |
Output is correct |
87 |
Correct |
156 ms |
7420 KB |
Output is correct |
88 |
Correct |
1510 ms |
8744 KB |
Output is correct |
89 |
Correct |
2069 ms |
10476 KB |
Output is correct |
90 |
Correct |
1481 ms |
8700 KB |
Output is correct |
91 |
Correct |
1399 ms |
6604 KB |
Output is correct |
92 |
Correct |
1447 ms |
6460 KB |
Output is correct |
93 |
Correct |
1950 ms |
6544 KB |
Output is correct |
94 |
Correct |
1793 ms |
8492 KB |
Output is correct |
95 |
Correct |
1837 ms |
8936 KB |
Output is correct |
96 |
Correct |
2044 ms |
8408 KB |
Output is correct |
97 |
Correct |
1079 ms |
8280 KB |
Output is correct |
98 |
Correct |
1153 ms |
8312 KB |
Output is correct |
99 |
Correct |
2063 ms |
9908 KB |
Output is correct |
100 |
Correct |
2079 ms |
10052 KB |
Output is correct |
101 |
Correct |
2092 ms |
10200 KB |
Output is correct |
102 |
Correct |
2116 ms |
9956 KB |
Output is correct |
103 |
Correct |
2281 ms |
8896 KB |
Output is correct |
104 |
Correct |
2246 ms |
8844 KB |
Output is correct |
105 |
Correct |
1636 ms |
8864 KB |
Output is correct |
106 |
Correct |
1317 ms |
8440 KB |
Output is correct |
107 |
Correct |
1513 ms |
8804 KB |
Output is correct |
108 |
Correct |
2100 ms |
9576 KB |
Output is correct |
109 |
Correct |
1607 ms |
7580 KB |
Output is correct |