#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
struct DSU {
int n;
vector<int> t;
vector<int> s;
vector<int> a, b;
void build(int _n) {
n = _n;
a.clear();
b.clear();
a.reserve(n);
b.reserve(n);
t.resize(n);
s.resize(n);
for (int i = 0; i < n; i += 1) {
t[i] = i;
s[i] = 1;
}
}
int get(int v) {
if (v == t[v]) {
return v;
}
return get(t[v]);
}
void merge(int u, int v, bool save) {
u = get(u);
v = get(v);
if (u == v) {
return;
}
if (s[u] > s[v]) {
swap(u, v);
}
t[u] = v;
s[v] += s[u];
if (save) {
a.push_back(u);
b.push_back(v);
}
}
void back() {
for (int i = (int)a.size() - 1; i >= 0; i -= 1) {
int u = a[i];
int v = b[i];
t[u] = u;
s[v] -= s[u];
}
a.clear();
b.clear();
}
int get_size(int v) {
return s[get(v)];
}
};
const int b = 500;
bool comp(const pair<ll, int> &a, const pair<ll, int> &b) {
return a > b;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, m;
cin >> n >> m;
vector<pair<int, int>> e(m);
vector<int> d(m);
for (int i = 0; i < m; i += 1) {
cin >> e[i].first >> e[i].second >> d[i];
--e[i].first;
--e[i].second;
}
int qs;
cin >> qs;
vector<array<int, 3>> q(qs);
for (int i = 0; i < qs; i += 1) {
cin >> q[i][0] >> q[i][1] >> q[i][2];
--q[i][1];
}
vector<int> rs(qs);
vector<pair<ll, int>> all_sorted(m);
for (int i = 0; i < m; i += 1) {
all_sorted[i] = make_pair(d[i], i);
}
sort(rall(all_sorted));
for (int l = 0; l < qs; l += b) {
int r = min(qs, l + b);
vector<int> chngd(m, 0);
for (int i = l; i < r; i += 1) {
if (q[i][0] == 1) {
chngd[q[i][1]] = true;
}
}
vector<pair<ll, int>> cnst_edgs;
vector<int> nd(m);
cnst_edgs.reserve(m);
vector<int> nt_cnst;
nt_cnst.reserve(b);
for (auto [_, i] : all_sorted) {
if (!chngd[i]) {
cnst_edgs.push_back(make_pair(d[i], i));
} else {
nt_cnst.push_back(i);
}
}
vector<pair<ll, int>> asks;
asks.reserve(b);
for (int i = l; i < r; i += 1) {
if (q[i][0] == 2) {
asks.push_back(make_pair(q[i][2], i));
}
}
sort(rall(asks));
int pos = 0;
DSU dsu;
dsu.build(n);
for (int i = 0; i < (int)asks.size(); i += 1) {
int f = asks[i].first;
while (pos < (int)cnst_edgs.size() && cnst_edgs[pos].first >= f) {
int t = cnst_edgs[pos].second;
dsu.merge(e[t].first, e[t].second, false);
pos += 1;
}
for (auto t : nt_cnst) {
nd[t] = d[t];
}
for (int j = l; j <= asks[i].second; j += 1) {
if (q[j][0] == 1) {
nd[q[j][1]] = q[j][2];
}
}
for (auto t : nt_cnst) {
if (nd[t] >= f) {
dsu.merge(e[t].first, e[t].second, true);
}
}
rs[asks[i].second] = dsu.get_size(q[asks[i].second][1]);
dsu.back();
}
for (int i = l; i < r; i += 1) {
if (q[i][0] == 1) {
d[q[i][1]] = q[i][2];
}
}
vector<pair<ll, int>> new_edgs;
for (auto t : nt_cnst) {
new_edgs.push_back(make_pair(d[t], t));
}
sort(rall(new_edgs));
merge(all(cnst_edgs), all(new_edgs), all_sorted.begin(), comp);
}
for (int i = 0; i < qs; i += 1) {
if (q[i][0] == 2) {
cout << rs[i] << "\n";
}
}
return 0;
}
Compilation message
bridges.cpp: In function 'int32_t main()':
bridges.cpp:120:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | for (auto [_, i] : all_sorted) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
12 ms |
616 KB |
Output is correct |
4 |
Correct |
5 ms |
596 KB |
Output is correct |
5 |
Correct |
8 ms |
632 KB |
Output is correct |
6 |
Correct |
6 ms |
592 KB |
Output is correct |
7 |
Correct |
7 ms |
596 KB |
Output is correct |
8 |
Correct |
8 ms |
596 KB |
Output is correct |
9 |
Correct |
8 ms |
588 KB |
Output is correct |
10 |
Correct |
8 ms |
584 KB |
Output is correct |
11 |
Correct |
8 ms |
548 KB |
Output is correct |
12 |
Correct |
8 ms |
588 KB |
Output is correct |
13 |
Correct |
11 ms |
596 KB |
Output is correct |
14 |
Correct |
9 ms |
596 KB |
Output is correct |
15 |
Correct |
9 ms |
648 KB |
Output is correct |
16 |
Correct |
8 ms |
572 KB |
Output is correct |
17 |
Correct |
8 ms |
592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
584 ms |
7656 KB |
Output is correct |
2 |
Correct |
582 ms |
7676 KB |
Output is correct |
3 |
Correct |
617 ms |
7676 KB |
Output is correct |
4 |
Correct |
587 ms |
7784 KB |
Output is correct |
5 |
Correct |
578 ms |
7676 KB |
Output is correct |
6 |
Correct |
682 ms |
7492 KB |
Output is correct |
7 |
Correct |
679 ms |
7668 KB |
Output is correct |
8 |
Correct |
681 ms |
7468 KB |
Output is correct |
9 |
Correct |
44 ms |
3380 KB |
Output is correct |
10 |
Correct |
450 ms |
6740 KB |
Output is correct |
11 |
Correct |
450 ms |
6560 KB |
Output is correct |
12 |
Correct |
559 ms |
7616 KB |
Output is correct |
13 |
Correct |
495 ms |
7656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
556 ms |
6276 KB |
Output is correct |
2 |
Correct |
303 ms |
4076 KB |
Output is correct |
3 |
Correct |
575 ms |
5996 KB |
Output is correct |
4 |
Correct |
503 ms |
6292 KB |
Output is correct |
5 |
Correct |
45 ms |
3392 KB |
Output is correct |
6 |
Correct |
531 ms |
6284 KB |
Output is correct |
7 |
Correct |
480 ms |
6140 KB |
Output is correct |
8 |
Correct |
464 ms |
6196 KB |
Output is correct |
9 |
Correct |
397 ms |
6096 KB |
Output is correct |
10 |
Correct |
379 ms |
6128 KB |
Output is correct |
11 |
Correct |
425 ms |
6124 KB |
Output is correct |
12 |
Correct |
364 ms |
6132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1004 ms |
11236 KB |
Output is correct |
2 |
Correct |
44 ms |
3380 KB |
Output is correct |
3 |
Correct |
96 ms |
7416 KB |
Output is correct |
4 |
Correct |
90 ms |
7540 KB |
Output is correct |
5 |
Correct |
899 ms |
9816 KB |
Output is correct |
6 |
Correct |
1014 ms |
11324 KB |
Output is correct |
7 |
Correct |
973 ms |
9692 KB |
Output is correct |
8 |
Correct |
467 ms |
7624 KB |
Output is correct |
9 |
Correct |
438 ms |
7712 KB |
Output is correct |
10 |
Correct |
458 ms |
7576 KB |
Output is correct |
11 |
Correct |
828 ms |
9360 KB |
Output is correct |
12 |
Correct |
770 ms |
9464 KB |
Output is correct |
13 |
Correct |
788 ms |
9208 KB |
Output is correct |
14 |
Correct |
950 ms |
9744 KB |
Output is correct |
15 |
Correct |
995 ms |
9756 KB |
Output is correct |
16 |
Correct |
1118 ms |
11144 KB |
Output is correct |
17 |
Correct |
1081 ms |
11148 KB |
Output is correct |
18 |
Correct |
1114 ms |
11284 KB |
Output is correct |
19 |
Correct |
1189 ms |
11200 KB |
Output is correct |
20 |
Correct |
895 ms |
9744 KB |
Output is correct |
21 |
Correct |
970 ms |
9696 KB |
Output is correct |
22 |
Correct |
1024 ms |
10896 KB |
Output is correct |
23 |
Correct |
875 ms |
8484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
584 ms |
7656 KB |
Output is correct |
2 |
Correct |
582 ms |
7676 KB |
Output is correct |
3 |
Correct |
617 ms |
7676 KB |
Output is correct |
4 |
Correct |
587 ms |
7784 KB |
Output is correct |
5 |
Correct |
578 ms |
7676 KB |
Output is correct |
6 |
Correct |
682 ms |
7492 KB |
Output is correct |
7 |
Correct |
679 ms |
7668 KB |
Output is correct |
8 |
Correct |
681 ms |
7468 KB |
Output is correct |
9 |
Correct |
44 ms |
3380 KB |
Output is correct |
10 |
Correct |
450 ms |
6740 KB |
Output is correct |
11 |
Correct |
450 ms |
6560 KB |
Output is correct |
12 |
Correct |
559 ms |
7616 KB |
Output is correct |
13 |
Correct |
495 ms |
7656 KB |
Output is correct |
14 |
Correct |
556 ms |
6276 KB |
Output is correct |
15 |
Correct |
303 ms |
4076 KB |
Output is correct |
16 |
Correct |
575 ms |
5996 KB |
Output is correct |
17 |
Correct |
503 ms |
6292 KB |
Output is correct |
18 |
Correct |
45 ms |
3392 KB |
Output is correct |
19 |
Correct |
531 ms |
6284 KB |
Output is correct |
20 |
Correct |
480 ms |
6140 KB |
Output is correct |
21 |
Correct |
464 ms |
6196 KB |
Output is correct |
22 |
Correct |
397 ms |
6096 KB |
Output is correct |
23 |
Correct |
379 ms |
6128 KB |
Output is correct |
24 |
Correct |
425 ms |
6124 KB |
Output is correct |
25 |
Correct |
364 ms |
6132 KB |
Output is correct |
26 |
Correct |
726 ms |
7656 KB |
Output is correct |
27 |
Correct |
752 ms |
7568 KB |
Output is correct |
28 |
Correct |
678 ms |
7644 KB |
Output is correct |
29 |
Correct |
595 ms |
7692 KB |
Output is correct |
30 |
Correct |
722 ms |
7544 KB |
Output is correct |
31 |
Correct |
769 ms |
7544 KB |
Output is correct |
32 |
Correct |
728 ms |
7480 KB |
Output is correct |
33 |
Correct |
692 ms |
7756 KB |
Output is correct |
34 |
Correct |
647 ms |
7676 KB |
Output is correct |
35 |
Correct |
702 ms |
7768 KB |
Output is correct |
36 |
Correct |
573 ms |
7664 KB |
Output is correct |
37 |
Correct |
566 ms |
7620 KB |
Output is correct |
38 |
Correct |
582 ms |
7744 KB |
Output is correct |
39 |
Correct |
510 ms |
7740 KB |
Output is correct |
40 |
Correct |
489 ms |
7740 KB |
Output is correct |
41 |
Correct |
547 ms |
7724 KB |
Output is correct |
42 |
Correct |
464 ms |
7632 KB |
Output is correct |
43 |
Correct |
464 ms |
7696 KB |
Output is correct |
44 |
Correct |
477 ms |
7620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
12 ms |
616 KB |
Output is correct |
4 |
Correct |
5 ms |
596 KB |
Output is correct |
5 |
Correct |
8 ms |
632 KB |
Output is correct |
6 |
Correct |
6 ms |
592 KB |
Output is correct |
7 |
Correct |
7 ms |
596 KB |
Output is correct |
8 |
Correct |
8 ms |
596 KB |
Output is correct |
9 |
Correct |
8 ms |
588 KB |
Output is correct |
10 |
Correct |
8 ms |
584 KB |
Output is correct |
11 |
Correct |
8 ms |
548 KB |
Output is correct |
12 |
Correct |
8 ms |
588 KB |
Output is correct |
13 |
Correct |
11 ms |
596 KB |
Output is correct |
14 |
Correct |
9 ms |
596 KB |
Output is correct |
15 |
Correct |
9 ms |
648 KB |
Output is correct |
16 |
Correct |
8 ms |
572 KB |
Output is correct |
17 |
Correct |
8 ms |
592 KB |
Output is correct |
18 |
Correct |
584 ms |
7656 KB |
Output is correct |
19 |
Correct |
582 ms |
7676 KB |
Output is correct |
20 |
Correct |
617 ms |
7676 KB |
Output is correct |
21 |
Correct |
587 ms |
7784 KB |
Output is correct |
22 |
Correct |
578 ms |
7676 KB |
Output is correct |
23 |
Correct |
682 ms |
7492 KB |
Output is correct |
24 |
Correct |
679 ms |
7668 KB |
Output is correct |
25 |
Correct |
681 ms |
7468 KB |
Output is correct |
26 |
Correct |
44 ms |
3380 KB |
Output is correct |
27 |
Correct |
450 ms |
6740 KB |
Output is correct |
28 |
Correct |
450 ms |
6560 KB |
Output is correct |
29 |
Correct |
559 ms |
7616 KB |
Output is correct |
30 |
Correct |
495 ms |
7656 KB |
Output is correct |
31 |
Correct |
556 ms |
6276 KB |
Output is correct |
32 |
Correct |
303 ms |
4076 KB |
Output is correct |
33 |
Correct |
575 ms |
5996 KB |
Output is correct |
34 |
Correct |
503 ms |
6292 KB |
Output is correct |
35 |
Correct |
45 ms |
3392 KB |
Output is correct |
36 |
Correct |
531 ms |
6284 KB |
Output is correct |
37 |
Correct |
480 ms |
6140 KB |
Output is correct |
38 |
Correct |
464 ms |
6196 KB |
Output is correct |
39 |
Correct |
397 ms |
6096 KB |
Output is correct |
40 |
Correct |
379 ms |
6128 KB |
Output is correct |
41 |
Correct |
425 ms |
6124 KB |
Output is correct |
42 |
Correct |
364 ms |
6132 KB |
Output is correct |
43 |
Correct |
1004 ms |
11236 KB |
Output is correct |
44 |
Correct |
44 ms |
3380 KB |
Output is correct |
45 |
Correct |
96 ms |
7416 KB |
Output is correct |
46 |
Correct |
90 ms |
7540 KB |
Output is correct |
47 |
Correct |
899 ms |
9816 KB |
Output is correct |
48 |
Correct |
1014 ms |
11324 KB |
Output is correct |
49 |
Correct |
973 ms |
9692 KB |
Output is correct |
50 |
Correct |
467 ms |
7624 KB |
Output is correct |
51 |
Correct |
438 ms |
7712 KB |
Output is correct |
52 |
Correct |
458 ms |
7576 KB |
Output is correct |
53 |
Correct |
828 ms |
9360 KB |
Output is correct |
54 |
Correct |
770 ms |
9464 KB |
Output is correct |
55 |
Correct |
788 ms |
9208 KB |
Output is correct |
56 |
Correct |
950 ms |
9744 KB |
Output is correct |
57 |
Correct |
995 ms |
9756 KB |
Output is correct |
58 |
Correct |
1118 ms |
11144 KB |
Output is correct |
59 |
Correct |
1081 ms |
11148 KB |
Output is correct |
60 |
Correct |
1114 ms |
11284 KB |
Output is correct |
61 |
Correct |
1189 ms |
11200 KB |
Output is correct |
62 |
Correct |
895 ms |
9744 KB |
Output is correct |
63 |
Correct |
970 ms |
9696 KB |
Output is correct |
64 |
Correct |
1024 ms |
10896 KB |
Output is correct |
65 |
Correct |
875 ms |
8484 KB |
Output is correct |
66 |
Correct |
726 ms |
7656 KB |
Output is correct |
67 |
Correct |
752 ms |
7568 KB |
Output is correct |
68 |
Correct |
678 ms |
7644 KB |
Output is correct |
69 |
Correct |
595 ms |
7692 KB |
Output is correct |
70 |
Correct |
722 ms |
7544 KB |
Output is correct |
71 |
Correct |
769 ms |
7544 KB |
Output is correct |
72 |
Correct |
728 ms |
7480 KB |
Output is correct |
73 |
Correct |
692 ms |
7756 KB |
Output is correct |
74 |
Correct |
647 ms |
7676 KB |
Output is correct |
75 |
Correct |
702 ms |
7768 KB |
Output is correct |
76 |
Correct |
573 ms |
7664 KB |
Output is correct |
77 |
Correct |
566 ms |
7620 KB |
Output is correct |
78 |
Correct |
582 ms |
7744 KB |
Output is correct |
79 |
Correct |
510 ms |
7740 KB |
Output is correct |
80 |
Correct |
489 ms |
7740 KB |
Output is correct |
81 |
Correct |
547 ms |
7724 KB |
Output is correct |
82 |
Correct |
464 ms |
7632 KB |
Output is correct |
83 |
Correct |
464 ms |
7696 KB |
Output is correct |
84 |
Correct |
477 ms |
7620 KB |
Output is correct |
85 |
Correct |
1173 ms |
11480 KB |
Output is correct |
86 |
Correct |
110 ms |
7456 KB |
Output is correct |
87 |
Correct |
99 ms |
7564 KB |
Output is correct |
88 |
Correct |
1085 ms |
9836 KB |
Output is correct |
89 |
Correct |
1134 ms |
11416 KB |
Output is correct |
90 |
Correct |
1016 ms |
9728 KB |
Output is correct |
91 |
Correct |
632 ms |
7680 KB |
Output is correct |
92 |
Correct |
621 ms |
7844 KB |
Output is correct |
93 |
Correct |
741 ms |
7620 KB |
Output is correct |
94 |
Correct |
938 ms |
9432 KB |
Output is correct |
95 |
Correct |
914 ms |
9548 KB |
Output is correct |
96 |
Correct |
927 ms |
9376 KB |
Output is correct |
97 |
Correct |
980 ms |
9804 KB |
Output is correct |
98 |
Correct |
939 ms |
9776 KB |
Output is correct |
99 |
Correct |
1184 ms |
11360 KB |
Output is correct |
100 |
Correct |
1235 ms |
11096 KB |
Output is correct |
101 |
Correct |
1182 ms |
11344 KB |
Output is correct |
102 |
Correct |
1175 ms |
11280 KB |
Output is correct |
103 |
Correct |
1066 ms |
10004 KB |
Output is correct |
104 |
Correct |
1161 ms |
9800 KB |
Output is correct |
105 |
Correct |
979 ms |
9976 KB |
Output is correct |
106 |
Correct |
788 ms |
9400 KB |
Output is correct |
107 |
Correct |
959 ms |
9948 KB |
Output is correct |
108 |
Correct |
1131 ms |
10936 KB |
Output is correct |
109 |
Correct |
973 ms |
8696 KB |
Output is correct |