#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 1e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
int n, m, i, u, v, w, q, t[N], x[N], y[N], uwu = 600, par[N], sz[N], mk[N], ans[N], j;
piii edge[N];
vi uc, ask, upd, qq[N];
stack <int> s;
int get (int u){
while (par[u] != u) u = par[u];
return u;
}
void update (int u, int v){
u = get(u);
v = get(v);
//cout << u << " " << v << "\n";
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
s.push(v);
par[v] = u;
sz[u] += sz[v];
}
void rollback (int pv){
while (s.size() > pv){
int u = s.top();
s.pop();
sz[par[u]] -= sz[u];
par[u] = u;
}
}
void rs (){
ask.clear();
upd.clear();
uc.clear();
memset(mk, 0, sizeof mk);
for (int h = 1; h <= n; h++)
par[h] = h, sz[h] = 1;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef hqm
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> n >> m;
forr (i, 1, m){
cin >> u >> v >> w;
edge[i] = {w, {u, v}};
}
cin >> q;
forr (i, 1, q)
cin >> t[i] >> x[i] >> y[i];
for (int i = 1; i <= q; i += uwu){
int lmt = min (i + uwu - 1, q);
rs();
forr (j, i, lmt)
if (t[j] == 1)
upd.pb(j);
forr (j, i, lmt)
if (t[j] == 1)
mk[x[j]] = 1, edge[x[j]].st = y[j];
else {
ask.pb(j);
for (int v : upd)
if (edge[x[v]].st >= y[j]) qq[j].pb(v);
}
forr (j, 1, m){
if (mk[j]) continue;
uc.pb(j);
}
sort(all(ask), [&](int u, int v) {return y[u] > y[v]; });
sort(all(uc), [&](int u, int v) {return edge[u].st > edge[v].st; });
int it = 0;
for (int u : ask){
while (it < uc.size() && edge[uc[it]].st >= y[u])
update (edge[uc[it]].nd.st, edge[uc[it]].nd.nd), it++;
int prev = s.size();
for (int v : qq[u]){
update(edge[x[v]].nd.st, edge[x[v]].nd.nd);
}
ans[u] = sz[get(x[u])];
rollback(prev);
}
}
forr (i, 1, q)
if (t[i] - 1)
cout << ans[i] << "\n";
return 0;
}
/*
*/
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:46:18: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | while (s.size() > pv){
| ~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:107:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | while (it < uc.size() && edge[uc[it]].st >= y[u])
| ~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
20 ms |
8956 KB |
Output is correct |
4 |
Correct |
3 ms |
4700 KB |
Output is correct |
5 |
Correct |
21 ms |
10188 KB |
Output is correct |
6 |
Correct |
15 ms |
10332 KB |
Output is correct |
7 |
Correct |
17 ms |
10536 KB |
Output is correct |
8 |
Correct |
21 ms |
8796 KB |
Output is correct |
9 |
Correct |
22 ms |
14680 KB |
Output is correct |
10 |
Correct |
21 ms |
9384 KB |
Output is correct |
11 |
Correct |
22 ms |
9044 KB |
Output is correct |
12 |
Correct |
27 ms |
10768 KB |
Output is correct |
13 |
Correct |
24 ms |
9712 KB |
Output is correct |
14 |
Correct |
23 ms |
8796 KB |
Output is correct |
15 |
Correct |
26 ms |
9300 KB |
Output is correct |
16 |
Correct |
23 ms |
12120 KB |
Output is correct |
17 |
Correct |
20 ms |
10844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1141 ms |
84296 KB |
Output is correct |
2 |
Correct |
1156 ms |
84144 KB |
Output is correct |
3 |
Correct |
1155 ms |
84284 KB |
Output is correct |
4 |
Correct |
1191 ms |
83904 KB |
Output is correct |
5 |
Correct |
1166 ms |
84184 KB |
Output is correct |
6 |
Correct |
1269 ms |
141348 KB |
Output is correct |
7 |
Correct |
1271 ms |
142128 KB |
Output is correct |
8 |
Correct |
1486 ms |
141532 KB |
Output is correct |
9 |
Correct |
27 ms |
5980 KB |
Output is correct |
10 |
Correct |
604 ms |
116220 KB |
Output is correct |
11 |
Correct |
608 ms |
100060 KB |
Output is correct |
12 |
Correct |
1042 ms |
71372 KB |
Output is correct |
13 |
Correct |
1022 ms |
80348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
777 ms |
72492 KB |
Output is correct |
2 |
Correct |
390 ms |
83796 KB |
Output is correct |
3 |
Correct |
808 ms |
101236 KB |
Output is correct |
4 |
Correct |
766 ms |
71912 KB |
Output is correct |
5 |
Correct |
26 ms |
5980 KB |
Output is correct |
6 |
Correct |
804 ms |
85636 KB |
Output is correct |
7 |
Correct |
741 ms |
66556 KB |
Output is correct |
8 |
Correct |
705 ms |
56044 KB |
Output is correct |
9 |
Correct |
651 ms |
49260 KB |
Output is correct |
10 |
Correct |
642 ms |
42776 KB |
Output is correct |
11 |
Correct |
648 ms |
47400 KB |
Output is correct |
12 |
Correct |
622 ms |
40728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2039 ms |
40864 KB |
Output is correct |
2 |
Correct |
27 ms |
7256 KB |
Output is correct |
3 |
Correct |
209 ms |
7384 KB |
Output is correct |
4 |
Correct |
87 ms |
7416 KB |
Output is correct |
5 |
Correct |
1016 ms |
43280 KB |
Output is correct |
6 |
Correct |
2001 ms |
44604 KB |
Output is correct |
7 |
Correct |
1020 ms |
42876 KB |
Output is correct |
8 |
Correct |
945 ms |
43516 KB |
Output is correct |
9 |
Correct |
924 ms |
43932 KB |
Output is correct |
10 |
Correct |
938 ms |
43428 KB |
Output is correct |
11 |
Correct |
1516 ms |
44444 KB |
Output is correct |
12 |
Correct |
1509 ms |
44564 KB |
Output is correct |
13 |
Correct |
1522 ms |
44484 KB |
Output is correct |
14 |
Correct |
920 ms |
43104 KB |
Output is correct |
15 |
Correct |
973 ms |
43040 KB |
Output is correct |
16 |
Correct |
2055 ms |
44940 KB |
Output is correct |
17 |
Correct |
2088 ms |
45060 KB |
Output is correct |
18 |
Correct |
2054 ms |
44956 KB |
Output is correct |
19 |
Correct |
2057 ms |
45308 KB |
Output is correct |
20 |
Correct |
1725 ms |
44604 KB |
Output is correct |
21 |
Correct |
1724 ms |
44324 KB |
Output is correct |
22 |
Correct |
1980 ms |
44048 KB |
Output is correct |
23 |
Correct |
1139 ms |
39672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1141 ms |
84296 KB |
Output is correct |
2 |
Correct |
1156 ms |
84144 KB |
Output is correct |
3 |
Correct |
1155 ms |
84284 KB |
Output is correct |
4 |
Correct |
1191 ms |
83904 KB |
Output is correct |
5 |
Correct |
1166 ms |
84184 KB |
Output is correct |
6 |
Correct |
1269 ms |
141348 KB |
Output is correct |
7 |
Correct |
1271 ms |
142128 KB |
Output is correct |
8 |
Correct |
1486 ms |
141532 KB |
Output is correct |
9 |
Correct |
27 ms |
5980 KB |
Output is correct |
10 |
Correct |
604 ms |
116220 KB |
Output is correct |
11 |
Correct |
608 ms |
100060 KB |
Output is correct |
12 |
Correct |
1042 ms |
71372 KB |
Output is correct |
13 |
Correct |
1022 ms |
80348 KB |
Output is correct |
14 |
Correct |
777 ms |
72492 KB |
Output is correct |
15 |
Correct |
390 ms |
83796 KB |
Output is correct |
16 |
Correct |
808 ms |
101236 KB |
Output is correct |
17 |
Correct |
766 ms |
71912 KB |
Output is correct |
18 |
Correct |
26 ms |
5980 KB |
Output is correct |
19 |
Correct |
804 ms |
85636 KB |
Output is correct |
20 |
Correct |
741 ms |
66556 KB |
Output is correct |
21 |
Correct |
705 ms |
56044 KB |
Output is correct |
22 |
Correct |
651 ms |
49260 KB |
Output is correct |
23 |
Correct |
642 ms |
42776 KB |
Output is correct |
24 |
Correct |
648 ms |
47400 KB |
Output is correct |
25 |
Correct |
622 ms |
40728 KB |
Output is correct |
26 |
Correct |
1122 ms |
84188 KB |
Output is correct |
27 |
Correct |
1247 ms |
113500 KB |
Output is correct |
28 |
Correct |
1184 ms |
83420 KB |
Output is correct |
29 |
Correct |
1052 ms |
55192 KB |
Output is correct |
30 |
Correct |
1215 ms |
99336 KB |
Output is correct |
31 |
Correct |
1222 ms |
102116 KB |
Output is correct |
32 |
Correct |
1221 ms |
102716 KB |
Output is correct |
33 |
Correct |
1174 ms |
82456 KB |
Output is correct |
34 |
Correct |
1167 ms |
82916 KB |
Output is correct |
35 |
Correct |
1187 ms |
83224 KB |
Output is correct |
36 |
Correct |
1054 ms |
59060 KB |
Output is correct |
37 |
Correct |
1055 ms |
58488 KB |
Output is correct |
38 |
Correct |
1056 ms |
57356 KB |
Output is correct |
39 |
Correct |
989 ms |
48168 KB |
Output is correct |
40 |
Correct |
982 ms |
47768 KB |
Output is correct |
41 |
Correct |
987 ms |
47360 KB |
Output is correct |
42 |
Correct |
952 ms |
45008 KB |
Output is correct |
43 |
Correct |
952 ms |
44832 KB |
Output is correct |
44 |
Correct |
947 ms |
44268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
20 ms |
8956 KB |
Output is correct |
4 |
Correct |
3 ms |
4700 KB |
Output is correct |
5 |
Correct |
21 ms |
10188 KB |
Output is correct |
6 |
Correct |
15 ms |
10332 KB |
Output is correct |
7 |
Correct |
17 ms |
10536 KB |
Output is correct |
8 |
Correct |
21 ms |
8796 KB |
Output is correct |
9 |
Correct |
22 ms |
14680 KB |
Output is correct |
10 |
Correct |
21 ms |
9384 KB |
Output is correct |
11 |
Correct |
22 ms |
9044 KB |
Output is correct |
12 |
Correct |
27 ms |
10768 KB |
Output is correct |
13 |
Correct |
24 ms |
9712 KB |
Output is correct |
14 |
Correct |
23 ms |
8796 KB |
Output is correct |
15 |
Correct |
26 ms |
9300 KB |
Output is correct |
16 |
Correct |
23 ms |
12120 KB |
Output is correct |
17 |
Correct |
20 ms |
10844 KB |
Output is correct |
18 |
Correct |
1141 ms |
84296 KB |
Output is correct |
19 |
Correct |
1156 ms |
84144 KB |
Output is correct |
20 |
Correct |
1155 ms |
84284 KB |
Output is correct |
21 |
Correct |
1191 ms |
83904 KB |
Output is correct |
22 |
Correct |
1166 ms |
84184 KB |
Output is correct |
23 |
Correct |
1269 ms |
141348 KB |
Output is correct |
24 |
Correct |
1271 ms |
142128 KB |
Output is correct |
25 |
Correct |
1486 ms |
141532 KB |
Output is correct |
26 |
Correct |
27 ms |
5980 KB |
Output is correct |
27 |
Correct |
604 ms |
116220 KB |
Output is correct |
28 |
Correct |
608 ms |
100060 KB |
Output is correct |
29 |
Correct |
1042 ms |
71372 KB |
Output is correct |
30 |
Correct |
1022 ms |
80348 KB |
Output is correct |
31 |
Correct |
777 ms |
72492 KB |
Output is correct |
32 |
Correct |
390 ms |
83796 KB |
Output is correct |
33 |
Correct |
808 ms |
101236 KB |
Output is correct |
34 |
Correct |
766 ms |
71912 KB |
Output is correct |
35 |
Correct |
26 ms |
5980 KB |
Output is correct |
36 |
Correct |
804 ms |
85636 KB |
Output is correct |
37 |
Correct |
741 ms |
66556 KB |
Output is correct |
38 |
Correct |
705 ms |
56044 KB |
Output is correct |
39 |
Correct |
651 ms |
49260 KB |
Output is correct |
40 |
Correct |
642 ms |
42776 KB |
Output is correct |
41 |
Correct |
648 ms |
47400 KB |
Output is correct |
42 |
Correct |
622 ms |
40728 KB |
Output is correct |
43 |
Correct |
2039 ms |
40864 KB |
Output is correct |
44 |
Correct |
27 ms |
7256 KB |
Output is correct |
45 |
Correct |
209 ms |
7384 KB |
Output is correct |
46 |
Correct |
87 ms |
7416 KB |
Output is correct |
47 |
Correct |
1016 ms |
43280 KB |
Output is correct |
48 |
Correct |
2001 ms |
44604 KB |
Output is correct |
49 |
Correct |
1020 ms |
42876 KB |
Output is correct |
50 |
Correct |
945 ms |
43516 KB |
Output is correct |
51 |
Correct |
924 ms |
43932 KB |
Output is correct |
52 |
Correct |
938 ms |
43428 KB |
Output is correct |
53 |
Correct |
1516 ms |
44444 KB |
Output is correct |
54 |
Correct |
1509 ms |
44564 KB |
Output is correct |
55 |
Correct |
1522 ms |
44484 KB |
Output is correct |
56 |
Correct |
920 ms |
43104 KB |
Output is correct |
57 |
Correct |
973 ms |
43040 KB |
Output is correct |
58 |
Correct |
2055 ms |
44940 KB |
Output is correct |
59 |
Correct |
2088 ms |
45060 KB |
Output is correct |
60 |
Correct |
2054 ms |
44956 KB |
Output is correct |
61 |
Correct |
2057 ms |
45308 KB |
Output is correct |
62 |
Correct |
1725 ms |
44604 KB |
Output is correct |
63 |
Correct |
1724 ms |
44324 KB |
Output is correct |
64 |
Correct |
1980 ms |
44048 KB |
Output is correct |
65 |
Correct |
1139 ms |
39672 KB |
Output is correct |
66 |
Correct |
1122 ms |
84188 KB |
Output is correct |
67 |
Correct |
1247 ms |
113500 KB |
Output is correct |
68 |
Correct |
1184 ms |
83420 KB |
Output is correct |
69 |
Correct |
1052 ms |
55192 KB |
Output is correct |
70 |
Correct |
1215 ms |
99336 KB |
Output is correct |
71 |
Correct |
1222 ms |
102116 KB |
Output is correct |
72 |
Correct |
1221 ms |
102716 KB |
Output is correct |
73 |
Correct |
1174 ms |
82456 KB |
Output is correct |
74 |
Correct |
1167 ms |
82916 KB |
Output is correct |
75 |
Correct |
1187 ms |
83224 KB |
Output is correct |
76 |
Correct |
1054 ms |
59060 KB |
Output is correct |
77 |
Correct |
1055 ms |
58488 KB |
Output is correct |
78 |
Correct |
1056 ms |
57356 KB |
Output is correct |
79 |
Correct |
989 ms |
48168 KB |
Output is correct |
80 |
Correct |
982 ms |
47768 KB |
Output is correct |
81 |
Correct |
987 ms |
47360 KB |
Output is correct |
82 |
Correct |
952 ms |
45008 KB |
Output is correct |
83 |
Correct |
952 ms |
44832 KB |
Output is correct |
84 |
Correct |
947 ms |
44268 KB |
Output is correct |
85 |
Correct |
2232 ms |
88428 KB |
Output is correct |
86 |
Correct |
225 ms |
11472 KB |
Output is correct |
87 |
Correct |
105 ms |
17184 KB |
Output is correct |
88 |
Correct |
1192 ms |
99288 KB |
Output is correct |
89 |
Correct |
2232 ms |
87152 KB |
Output is correct |
90 |
Correct |
1238 ms |
99976 KB |
Output is correct |
91 |
Correct |
1178 ms |
87004 KB |
Output is correct |
92 |
Correct |
1182 ms |
86748 KB |
Output is correct |
93 |
Correct |
1308 ms |
144172 KB |
Output is correct |
94 |
Correct |
1760 ms |
88004 KB |
Output is correct |
95 |
Correct |
1746 ms |
87996 KB |
Output is correct |
96 |
Correct |
1761 ms |
144532 KB |
Output is correct |
97 |
Correct |
1121 ms |
63560 KB |
Output is correct |
98 |
Correct |
1097 ms |
65512 KB |
Output is correct |
99 |
Correct |
2263 ms |
89496 KB |
Output is correct |
100 |
Correct |
2293 ms |
88308 KB |
Output is correct |
101 |
Correct |
2345 ms |
88404 KB |
Output is correct |
102 |
Correct |
2299 ms |
88252 KB |
Output is correct |
103 |
Correct |
2001 ms |
145100 KB |
Output is correct |
104 |
Correct |
1982 ms |
145100 KB |
Output is correct |
105 |
Correct |
1824 ms |
84628 KB |
Output is correct |
106 |
Correct |
1567 ms |
64280 KB |
Output is correct |
107 |
Correct |
1804 ms |
73024 KB |
Output is correct |
108 |
Correct |
2174 ms |
115752 KB |
Output is correct |
109 |
Correct |
1321 ms |
137612 KB |
Output is correct |