#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 1e5 + 5;
const int K = 1000;
int n, m, q;
int ans[SIZE];
int a[SIZE], b[SIZE], w[SIZE];
int t[SIZE], p[SIZE], x[SIZE];
bool is[SIZE];
vector<int> op[SIZE];
int to[SIZE], sz[SIZE];
vector<int> st;
int dsu(int x) {
while (x != to[x]) x = to[x];
return x;
}
void Merge(int a, int b) {
a = dsu(a), b = dsu(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
st.pb(b);
to[b] = a, sz[a] += sz[b];
}
void rollback(int ver) {
while (st.size() > ver) {
int x = st.back();
st.pop_back();
sz[to[x]] -= sz[x];
to[x] = x;
}
}
void solve() {
cin >> n >> m;
FOR (i, 1, m) cin >> a[i] >> b[i] >> w[i];
cin >> q;
FOR (i, 1, q) cin >> t[i] >> p[i] >> x[i];
iota(to + 1, to + n + 1, 1);
fill(sz + 1, sz + n + 1, 1);
for (int l = 1; l <= q; l += K) {
int r = min(l + K - 1, q);
vector<int> v1, v2, que;
FOR (i, l, r) {
if (t[i] == 1) is[p[i]] = 1, v2.pb(p[i]);
else que.pb(i);
}
FOR (i, l, r) {
if (t[i] == 1) w[p[i]] = x[i];
else for (int id : v2) if (w[id] >= x[i]) op[i].pb(id);
}
FOR (i, 1, m) if (!is[i]) v1.pb(i);
sort(v1.begin(), v1.end(), [](int lhs, int rhs) {
return w[lhs] > w[rhs];
});
sort(que.begin(), que.end(), [](int lhs, int rhs) {
return x[lhs] > x[rhs];
});
int rp = 0;
for (int id : que) {
while (rp < v1.size() && w[v1[rp]] >= x[id]) {
Merge(a[v1[rp]], b[v1[rp]]);
rp++;
}
int ver = st.size();
for (int p : op[id]) Merge(a[p], b[p]);
ans[id] = sz[dsu(p[id])];
rollback(ver);
}
rollback(0);
FOR (i, l, r) if (t[i] == 1) is[p[i]] = 0;
}
FOR (i, 1, q) if (ans[i]) cout << ans[i] << '\n';
}
int main() {
Waimai;
solve();
}
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:46:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | while (st.size() > ver) {
| ~~~~~~~~~~^~~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | while (rp < v1.size() && w[v1[rp]] >= x[id]) {
| ~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
34 ms |
9520 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
35 ms |
10240 KB |
Output is correct |
6 |
Correct |
25 ms |
10392 KB |
Output is correct |
7 |
Correct |
31 ms |
10456 KB |
Output is correct |
8 |
Correct |
36 ms |
8820 KB |
Output is correct |
9 |
Correct |
43 ms |
14784 KB |
Output is correct |
10 |
Correct |
36 ms |
9680 KB |
Output is correct |
11 |
Correct |
36 ms |
9444 KB |
Output is correct |
12 |
Correct |
44 ms |
11980 KB |
Output is correct |
13 |
Correct |
42 ms |
10096 KB |
Output is correct |
14 |
Correct |
39 ms |
9236 KB |
Output is correct |
15 |
Correct |
43 ms |
10096 KB |
Output is correct |
16 |
Correct |
39 ms |
12932 KB |
Output is correct |
17 |
Correct |
38 ms |
12112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1241 ms |
72972 KB |
Output is correct |
2 |
Correct |
1266 ms |
72896 KB |
Output is correct |
3 |
Correct |
1248 ms |
73168 KB |
Output is correct |
4 |
Correct |
1322 ms |
72660 KB |
Output is correct |
5 |
Correct |
1332 ms |
73324 KB |
Output is correct |
6 |
Correct |
1856 ms |
130748 KB |
Output is correct |
7 |
Correct |
1817 ms |
127488 KB |
Output is correct |
8 |
Correct |
1833 ms |
127256 KB |
Output is correct |
9 |
Correct |
32 ms |
4428 KB |
Output is correct |
10 |
Correct |
1028 ms |
98988 KB |
Output is correct |
11 |
Correct |
990 ms |
98388 KB |
Output is correct |
12 |
Correct |
1085 ms |
52644 KB |
Output is correct |
13 |
Correct |
1076 ms |
46140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
990 ms |
72716 KB |
Output is correct |
2 |
Correct |
728 ms |
97864 KB |
Output is correct |
3 |
Correct |
1165 ms |
100792 KB |
Output is correct |
4 |
Correct |
960 ms |
72280 KB |
Output is correct |
5 |
Correct |
33 ms |
4392 KB |
Output is correct |
6 |
Correct |
1103 ms |
92032 KB |
Output is correct |
7 |
Correct |
886 ms |
64144 KB |
Output is correct |
8 |
Correct |
787 ms |
48648 KB |
Output is correct |
9 |
Correct |
644 ms |
40268 KB |
Output is correct |
10 |
Correct |
600 ms |
28652 KB |
Output is correct |
11 |
Correct |
668 ms |
38060 KB |
Output is correct |
12 |
Correct |
591 ms |
27820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1435 ms |
7344 KB |
Output is correct |
2 |
Correct |
39 ms |
4332 KB |
Output is correct |
3 |
Correct |
156 ms |
4908 KB |
Output is correct |
4 |
Correct |
67 ms |
4936 KB |
Output is correct |
5 |
Correct |
710 ms |
7404 KB |
Output is correct |
6 |
Correct |
1354 ms |
7460 KB |
Output is correct |
7 |
Correct |
691 ms |
7528 KB |
Output is correct |
8 |
Correct |
735 ms |
5864 KB |
Output is correct |
9 |
Correct |
718 ms |
5932 KB |
Output is correct |
10 |
Correct |
736 ms |
5964 KB |
Output is correct |
11 |
Correct |
1044 ms |
6668 KB |
Output is correct |
12 |
Correct |
1027 ms |
6824 KB |
Output is correct |
13 |
Correct |
1051 ms |
7064 KB |
Output is correct |
14 |
Correct |
622 ms |
7376 KB |
Output is correct |
15 |
Correct |
677 ms |
7412 KB |
Output is correct |
16 |
Correct |
1366 ms |
7416 KB |
Output is correct |
17 |
Correct |
1419 ms |
7304 KB |
Output is correct |
18 |
Correct |
1439 ms |
7476 KB |
Output is correct |
19 |
Correct |
1427 ms |
7368 KB |
Output is correct |
20 |
Correct |
1228 ms |
7316 KB |
Output is correct |
21 |
Correct |
1172 ms |
7308 KB |
Output is correct |
22 |
Correct |
1337 ms |
7300 KB |
Output is correct |
23 |
Correct |
797 ms |
7068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1241 ms |
72972 KB |
Output is correct |
2 |
Correct |
1266 ms |
72896 KB |
Output is correct |
3 |
Correct |
1248 ms |
73168 KB |
Output is correct |
4 |
Correct |
1322 ms |
72660 KB |
Output is correct |
5 |
Correct |
1332 ms |
73324 KB |
Output is correct |
6 |
Correct |
1856 ms |
130748 KB |
Output is correct |
7 |
Correct |
1817 ms |
127488 KB |
Output is correct |
8 |
Correct |
1833 ms |
127256 KB |
Output is correct |
9 |
Correct |
32 ms |
4428 KB |
Output is correct |
10 |
Correct |
1028 ms |
98988 KB |
Output is correct |
11 |
Correct |
990 ms |
98388 KB |
Output is correct |
12 |
Correct |
1085 ms |
52644 KB |
Output is correct |
13 |
Correct |
1076 ms |
46140 KB |
Output is correct |
14 |
Correct |
990 ms |
72716 KB |
Output is correct |
15 |
Correct |
728 ms |
97864 KB |
Output is correct |
16 |
Correct |
1165 ms |
100792 KB |
Output is correct |
17 |
Correct |
960 ms |
72280 KB |
Output is correct |
18 |
Correct |
33 ms |
4392 KB |
Output is correct |
19 |
Correct |
1103 ms |
92032 KB |
Output is correct |
20 |
Correct |
886 ms |
64144 KB |
Output is correct |
21 |
Correct |
787 ms |
48648 KB |
Output is correct |
22 |
Correct |
644 ms |
40268 KB |
Output is correct |
23 |
Correct |
600 ms |
28652 KB |
Output is correct |
24 |
Correct |
668 ms |
38060 KB |
Output is correct |
25 |
Correct |
591 ms |
27820 KB |
Output is correct |
26 |
Correct |
1274 ms |
73064 KB |
Output is correct |
27 |
Correct |
1628 ms |
102328 KB |
Output is correct |
28 |
Correct |
1372 ms |
71324 KB |
Output is correct |
29 |
Correct |
971 ms |
28496 KB |
Output is correct |
30 |
Correct |
1526 ms |
88804 KB |
Output is correct |
31 |
Correct |
1545 ms |
91104 KB |
Output is correct |
32 |
Correct |
1564 ms |
91848 KB |
Output is correct |
33 |
Correct |
1325 ms |
71800 KB |
Output is correct |
34 |
Correct |
1337 ms |
71628 KB |
Output is correct |
35 |
Correct |
1336 ms |
71948 KB |
Output is correct |
36 |
Correct |
1020 ms |
35476 KB |
Output is correct |
37 |
Correct |
1016 ms |
34164 KB |
Output is correct |
38 |
Correct |
984 ms |
32496 KB |
Output is correct |
39 |
Correct |
841 ms |
18488 KB |
Output is correct |
40 |
Correct |
837 ms |
17636 KB |
Output is correct |
41 |
Correct |
838 ms |
16984 KB |
Output is correct |
42 |
Correct |
826 ms |
16948 KB |
Output is correct |
43 |
Correct |
826 ms |
16368 KB |
Output is correct |
44 |
Correct |
830 ms |
15632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
34 ms |
9520 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
35 ms |
10240 KB |
Output is correct |
6 |
Correct |
25 ms |
10392 KB |
Output is correct |
7 |
Correct |
31 ms |
10456 KB |
Output is correct |
8 |
Correct |
36 ms |
8820 KB |
Output is correct |
9 |
Correct |
43 ms |
14784 KB |
Output is correct |
10 |
Correct |
36 ms |
9680 KB |
Output is correct |
11 |
Correct |
36 ms |
9444 KB |
Output is correct |
12 |
Correct |
44 ms |
11980 KB |
Output is correct |
13 |
Correct |
42 ms |
10096 KB |
Output is correct |
14 |
Correct |
39 ms |
9236 KB |
Output is correct |
15 |
Correct |
43 ms |
10096 KB |
Output is correct |
16 |
Correct |
39 ms |
12932 KB |
Output is correct |
17 |
Correct |
38 ms |
12112 KB |
Output is correct |
18 |
Correct |
1241 ms |
72972 KB |
Output is correct |
19 |
Correct |
1266 ms |
72896 KB |
Output is correct |
20 |
Correct |
1248 ms |
73168 KB |
Output is correct |
21 |
Correct |
1322 ms |
72660 KB |
Output is correct |
22 |
Correct |
1332 ms |
73324 KB |
Output is correct |
23 |
Correct |
1856 ms |
130748 KB |
Output is correct |
24 |
Correct |
1817 ms |
127488 KB |
Output is correct |
25 |
Correct |
1833 ms |
127256 KB |
Output is correct |
26 |
Correct |
32 ms |
4428 KB |
Output is correct |
27 |
Correct |
1028 ms |
98988 KB |
Output is correct |
28 |
Correct |
990 ms |
98388 KB |
Output is correct |
29 |
Correct |
1085 ms |
52644 KB |
Output is correct |
30 |
Correct |
1076 ms |
46140 KB |
Output is correct |
31 |
Correct |
990 ms |
72716 KB |
Output is correct |
32 |
Correct |
728 ms |
97864 KB |
Output is correct |
33 |
Correct |
1165 ms |
100792 KB |
Output is correct |
34 |
Correct |
960 ms |
72280 KB |
Output is correct |
35 |
Correct |
33 ms |
4392 KB |
Output is correct |
36 |
Correct |
1103 ms |
92032 KB |
Output is correct |
37 |
Correct |
886 ms |
64144 KB |
Output is correct |
38 |
Correct |
787 ms |
48648 KB |
Output is correct |
39 |
Correct |
644 ms |
40268 KB |
Output is correct |
40 |
Correct |
600 ms |
28652 KB |
Output is correct |
41 |
Correct |
668 ms |
38060 KB |
Output is correct |
42 |
Correct |
591 ms |
27820 KB |
Output is correct |
43 |
Correct |
1435 ms |
7344 KB |
Output is correct |
44 |
Correct |
39 ms |
4332 KB |
Output is correct |
45 |
Correct |
156 ms |
4908 KB |
Output is correct |
46 |
Correct |
67 ms |
4936 KB |
Output is correct |
47 |
Correct |
710 ms |
7404 KB |
Output is correct |
48 |
Correct |
1354 ms |
7460 KB |
Output is correct |
49 |
Correct |
691 ms |
7528 KB |
Output is correct |
50 |
Correct |
735 ms |
5864 KB |
Output is correct |
51 |
Correct |
718 ms |
5932 KB |
Output is correct |
52 |
Correct |
736 ms |
5964 KB |
Output is correct |
53 |
Correct |
1044 ms |
6668 KB |
Output is correct |
54 |
Correct |
1027 ms |
6824 KB |
Output is correct |
55 |
Correct |
1051 ms |
7064 KB |
Output is correct |
56 |
Correct |
622 ms |
7376 KB |
Output is correct |
57 |
Correct |
677 ms |
7412 KB |
Output is correct |
58 |
Correct |
1366 ms |
7416 KB |
Output is correct |
59 |
Correct |
1419 ms |
7304 KB |
Output is correct |
60 |
Correct |
1439 ms |
7476 KB |
Output is correct |
61 |
Correct |
1427 ms |
7368 KB |
Output is correct |
62 |
Correct |
1228 ms |
7316 KB |
Output is correct |
63 |
Correct |
1172 ms |
7308 KB |
Output is correct |
64 |
Correct |
1337 ms |
7300 KB |
Output is correct |
65 |
Correct |
797 ms |
7068 KB |
Output is correct |
66 |
Correct |
1274 ms |
73064 KB |
Output is correct |
67 |
Correct |
1628 ms |
102328 KB |
Output is correct |
68 |
Correct |
1372 ms |
71324 KB |
Output is correct |
69 |
Correct |
971 ms |
28496 KB |
Output is correct |
70 |
Correct |
1526 ms |
88804 KB |
Output is correct |
71 |
Correct |
1545 ms |
91104 KB |
Output is correct |
72 |
Correct |
1564 ms |
91848 KB |
Output is correct |
73 |
Correct |
1325 ms |
71800 KB |
Output is correct |
74 |
Correct |
1337 ms |
71628 KB |
Output is correct |
75 |
Correct |
1336 ms |
71948 KB |
Output is correct |
76 |
Correct |
1020 ms |
35476 KB |
Output is correct |
77 |
Correct |
1016 ms |
34164 KB |
Output is correct |
78 |
Correct |
984 ms |
32496 KB |
Output is correct |
79 |
Correct |
841 ms |
18488 KB |
Output is correct |
80 |
Correct |
837 ms |
17636 KB |
Output is correct |
81 |
Correct |
838 ms |
16984 KB |
Output is correct |
82 |
Correct |
826 ms |
16948 KB |
Output is correct |
83 |
Correct |
826 ms |
16368 KB |
Output is correct |
84 |
Correct |
830 ms |
15632 KB |
Output is correct |
85 |
Correct |
1893 ms |
74116 KB |
Output is correct |
86 |
Correct |
169 ms |
11676 KB |
Output is correct |
87 |
Correct |
102 ms |
16032 KB |
Output is correct |
88 |
Correct |
1089 ms |
87704 KB |
Output is correct |
89 |
Correct |
1825 ms |
72868 KB |
Output is correct |
90 |
Correct |
1106 ms |
98624 KB |
Output is correct |
91 |
Correct |
1398 ms |
75596 KB |
Output is correct |
92 |
Correct |
1378 ms |
75856 KB |
Output is correct |
93 |
Correct |
1955 ms |
113180 KB |
Output is correct |
94 |
Correct |
1615 ms |
77016 KB |
Output is correct |
95 |
Correct |
1586 ms |
76904 KB |
Output is correct |
96 |
Correct |
1823 ms |
117616 KB |
Output is correct |
97 |
Correct |
858 ms |
42236 KB |
Output is correct |
98 |
Correct |
895 ms |
39572 KB |
Output is correct |
99 |
Correct |
1832 ms |
78928 KB |
Output is correct |
100 |
Correct |
1894 ms |
77764 KB |
Output is correct |
101 |
Correct |
1932 ms |
77820 KB |
Output is correct |
102 |
Correct |
1912 ms |
77876 KB |
Output is correct |
103 |
Correct |
1966 ms |
122932 KB |
Output is correct |
104 |
Correct |
1993 ms |
122548 KB |
Output is correct |
105 |
Correct |
1496 ms |
50296 KB |
Output is correct |
106 |
Correct |
1233 ms |
30516 KB |
Output is correct |
107 |
Correct |
1421 ms |
56596 KB |
Output is correct |
108 |
Correct |
1870 ms |
112948 KB |
Output is correct |
109 |
Correct |
1337 ms |
116716 KB |
Output is correct |