#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
#define BKT 690
int n, m, qrys;
int a[100069], b[100069];
int w[100069];
int t[100069], p[100069], q[100069];
int ans[100069];
vector<int> ext[100069];
int par[100069], sz[100069];
vector<pair<int,int>> lg;
int fnd(int x) {
return x == par[x] ? x : fnd(par[x]); //don't compress
}
void merge(int x, int y) {
x = fnd(x); y = fnd(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
lg.push_back({x, y});
par[y] = x;
sz[x] += sz[y];
}
void calc(int x) {
lg.clear();
for (auto i : ext[x]) {
merge(a[i], b[i]);
}
ans[x] = sz[fnd(p[x])];
reverse(all(lg));
for (auto [x, y] : lg) {
sz[x] -= sz[y];
par[y] = y;
}
}
vector<pair<int,int>> vctr;
void solve(int tl, int tr) {
set<int> spec;
vctr.clear();
for (int i = tl; i < tr; i++) if (t[i] == 1) {
spec.insert(p[i]);
}
for (int i = tl; i < tr; i++) {
if (t[i] == 1) {
w[p[i]] = q[i];
continue;
}
for (auto t : spec) {
if (w[t] >= q[i]) {
ext[i].push_back(t);
}
}
vctr.push_back({q[i], i - 100069});
}
for (int i = 0; i < m; i++) {
if (spec.find(i) == spec.end()) vctr.push_back({w[i], i});
}
sort(all(vctr), greater<pair<int,int>>());
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
for (auto t : vctr) {
if (t.s >= 0) {
merge(a[t.s], b[t.s]);
}
else {
calc(t.s + 100069);
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin>>n>>m;
for (int i = 0; i < m; i++) {
cin>>a[i]>>b[i]>>w[i];
a[i]--; b[i]--;
}
cin>>qrys;
for (int i = 0; i < qrys; i++) {
cin>>t[i]>>p[i]>>q[i];
p[i]--;
}
for (int i = 0; i < qrys; i += BKT) {
solve(i, min(i + BKT, qrys));
}
for (int i = 0; i < qrys; i++) {
if (t[i] == 2) cout<<ans[i]<<endl;
}
return 0;
}
Compilation message
bridges.cpp: In function 'void calc(int)':
bridges.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for (auto [x, y] : lg) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
27 ms |
7120 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
11 ms |
4504 KB |
Output is correct |
6 |
Correct |
10 ms |
4564 KB |
Output is correct |
7 |
Correct |
11 ms |
4492 KB |
Output is correct |
8 |
Correct |
12 ms |
4368 KB |
Output is correct |
9 |
Correct |
12 ms |
5448 KB |
Output is correct |
10 |
Correct |
12 ms |
4436 KB |
Output is correct |
11 |
Correct |
14 ms |
4368 KB |
Output is correct |
12 |
Correct |
13 ms |
4812 KB |
Output is correct |
13 |
Correct |
16 ms |
5136 KB |
Output is correct |
14 |
Correct |
15 ms |
4796 KB |
Output is correct |
15 |
Correct |
13 ms |
4484 KB |
Output is correct |
16 |
Correct |
12 ms |
4820 KB |
Output is correct |
17 |
Correct |
12 ms |
4820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1066 ms |
59556 KB |
Output is correct |
2 |
Correct |
1027 ms |
59456 KB |
Output is correct |
3 |
Correct |
1031 ms |
59648 KB |
Output is correct |
4 |
Correct |
1037 ms |
59392 KB |
Output is correct |
5 |
Correct |
1022 ms |
59656 KB |
Output is correct |
6 |
Correct |
1142 ms |
109604 KB |
Output is correct |
7 |
Correct |
1113 ms |
109936 KB |
Output is correct |
8 |
Correct |
1225 ms |
109836 KB |
Output is correct |
9 |
Correct |
27 ms |
5804 KB |
Output is correct |
10 |
Correct |
895 ms |
83464 KB |
Output is correct |
11 |
Correct |
947 ms |
67648 KB |
Output is correct |
12 |
Correct |
861 ms |
49160 KB |
Output is correct |
13 |
Correct |
878 ms |
48852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
816 ms |
58776 KB |
Output is correct |
2 |
Correct |
473 ms |
81752 KB |
Output is correct |
3 |
Correct |
818 ms |
83532 KB |
Output is correct |
4 |
Correct |
773 ms |
58468 KB |
Output is correct |
5 |
Correct |
27 ms |
5708 KB |
Output is correct |
6 |
Correct |
823 ms |
74200 KB |
Output is correct |
7 |
Correct |
757 ms |
51544 KB |
Output is correct |
8 |
Correct |
681 ms |
39508 KB |
Output is correct |
9 |
Correct |
570 ms |
31316 KB |
Output is correct |
10 |
Correct |
552 ms |
23692 KB |
Output is correct |
11 |
Correct |
593 ms |
31228 KB |
Output is correct |
12 |
Correct |
567 ms |
23404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1606 ms |
10896 KB |
Output is correct |
2 |
Correct |
26 ms |
5844 KB |
Output is correct |
3 |
Correct |
169 ms |
6924 KB |
Output is correct |
4 |
Correct |
104 ms |
7084 KB |
Output is correct |
5 |
Correct |
1601 ms |
9720 KB |
Output is correct |
6 |
Correct |
1554 ms |
10872 KB |
Output is correct |
7 |
Correct |
1583 ms |
9856 KB |
Output is correct |
8 |
Correct |
735 ms |
8644 KB |
Output is correct |
9 |
Correct |
727 ms |
8692 KB |
Output is correct |
10 |
Correct |
737 ms |
9008 KB |
Output is correct |
11 |
Correct |
1176 ms |
9796 KB |
Output is correct |
12 |
Correct |
1168 ms |
9780 KB |
Output is correct |
13 |
Correct |
1168 ms |
10584 KB |
Output is correct |
14 |
Correct |
1367 ms |
10164 KB |
Output is correct |
15 |
Correct |
1480 ms |
10068 KB |
Output is correct |
16 |
Correct |
1640 ms |
10900 KB |
Output is correct |
17 |
Correct |
1608 ms |
10856 KB |
Output is correct |
18 |
Correct |
1579 ms |
11076 KB |
Output is correct |
19 |
Correct |
1566 ms |
10908 KB |
Output is correct |
20 |
Correct |
1367 ms |
10840 KB |
Output is correct |
21 |
Correct |
1340 ms |
10768 KB |
Output is correct |
22 |
Correct |
1531 ms |
11500 KB |
Output is correct |
23 |
Correct |
1418 ms |
9628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1066 ms |
59556 KB |
Output is correct |
2 |
Correct |
1027 ms |
59456 KB |
Output is correct |
3 |
Correct |
1031 ms |
59648 KB |
Output is correct |
4 |
Correct |
1037 ms |
59392 KB |
Output is correct |
5 |
Correct |
1022 ms |
59656 KB |
Output is correct |
6 |
Correct |
1142 ms |
109604 KB |
Output is correct |
7 |
Correct |
1113 ms |
109936 KB |
Output is correct |
8 |
Correct |
1225 ms |
109836 KB |
Output is correct |
9 |
Correct |
27 ms |
5804 KB |
Output is correct |
10 |
Correct |
895 ms |
83464 KB |
Output is correct |
11 |
Correct |
947 ms |
67648 KB |
Output is correct |
12 |
Correct |
861 ms |
49160 KB |
Output is correct |
13 |
Correct |
878 ms |
48852 KB |
Output is correct |
14 |
Correct |
816 ms |
58776 KB |
Output is correct |
15 |
Correct |
473 ms |
81752 KB |
Output is correct |
16 |
Correct |
818 ms |
83532 KB |
Output is correct |
17 |
Correct |
773 ms |
58468 KB |
Output is correct |
18 |
Correct |
27 ms |
5708 KB |
Output is correct |
19 |
Correct |
823 ms |
74200 KB |
Output is correct |
20 |
Correct |
757 ms |
51544 KB |
Output is correct |
21 |
Correct |
681 ms |
39508 KB |
Output is correct |
22 |
Correct |
570 ms |
31316 KB |
Output is correct |
23 |
Correct |
552 ms |
23692 KB |
Output is correct |
24 |
Correct |
593 ms |
31228 KB |
Output is correct |
25 |
Correct |
567 ms |
23404 KB |
Output is correct |
26 |
Correct |
1051 ms |
59244 KB |
Output is correct |
27 |
Correct |
1151 ms |
84912 KB |
Output is correct |
28 |
Correct |
1106 ms |
58088 KB |
Output is correct |
29 |
Correct |
955 ms |
25420 KB |
Output is correct |
30 |
Correct |
1127 ms |
72688 KB |
Output is correct |
31 |
Correct |
1126 ms |
75192 KB |
Output is correct |
32 |
Correct |
1139 ms |
75652 KB |
Output is correct |
33 |
Correct |
1096 ms |
57600 KB |
Output is correct |
34 |
Correct |
1102 ms |
58112 KB |
Output is correct |
35 |
Correct |
1100 ms |
58208 KB |
Output is correct |
36 |
Correct |
992 ms |
30440 KB |
Output is correct |
37 |
Correct |
1004 ms |
29336 KB |
Output is correct |
38 |
Correct |
968 ms |
28160 KB |
Output is correct |
39 |
Correct |
812 ms |
17272 KB |
Output is correct |
40 |
Correct |
819 ms |
16688 KB |
Output is correct |
41 |
Correct |
814 ms |
16376 KB |
Output is correct |
42 |
Correct |
830 ms |
16208 KB |
Output is correct |
43 |
Correct |
832 ms |
15768 KB |
Output is correct |
44 |
Correct |
831 ms |
15436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
27 ms |
7120 KB |
Output is correct |
4 |
Correct |
4 ms |
3028 KB |
Output is correct |
5 |
Correct |
11 ms |
4504 KB |
Output is correct |
6 |
Correct |
10 ms |
4564 KB |
Output is correct |
7 |
Correct |
11 ms |
4492 KB |
Output is correct |
8 |
Correct |
12 ms |
4368 KB |
Output is correct |
9 |
Correct |
12 ms |
5448 KB |
Output is correct |
10 |
Correct |
12 ms |
4436 KB |
Output is correct |
11 |
Correct |
14 ms |
4368 KB |
Output is correct |
12 |
Correct |
13 ms |
4812 KB |
Output is correct |
13 |
Correct |
16 ms |
5136 KB |
Output is correct |
14 |
Correct |
15 ms |
4796 KB |
Output is correct |
15 |
Correct |
13 ms |
4484 KB |
Output is correct |
16 |
Correct |
12 ms |
4820 KB |
Output is correct |
17 |
Correct |
12 ms |
4820 KB |
Output is correct |
18 |
Correct |
1066 ms |
59556 KB |
Output is correct |
19 |
Correct |
1027 ms |
59456 KB |
Output is correct |
20 |
Correct |
1031 ms |
59648 KB |
Output is correct |
21 |
Correct |
1037 ms |
59392 KB |
Output is correct |
22 |
Correct |
1022 ms |
59656 KB |
Output is correct |
23 |
Correct |
1142 ms |
109604 KB |
Output is correct |
24 |
Correct |
1113 ms |
109936 KB |
Output is correct |
25 |
Correct |
1225 ms |
109836 KB |
Output is correct |
26 |
Correct |
27 ms |
5804 KB |
Output is correct |
27 |
Correct |
895 ms |
83464 KB |
Output is correct |
28 |
Correct |
947 ms |
67648 KB |
Output is correct |
29 |
Correct |
861 ms |
49160 KB |
Output is correct |
30 |
Correct |
878 ms |
48852 KB |
Output is correct |
31 |
Correct |
816 ms |
58776 KB |
Output is correct |
32 |
Correct |
473 ms |
81752 KB |
Output is correct |
33 |
Correct |
818 ms |
83532 KB |
Output is correct |
34 |
Correct |
773 ms |
58468 KB |
Output is correct |
35 |
Correct |
27 ms |
5708 KB |
Output is correct |
36 |
Correct |
823 ms |
74200 KB |
Output is correct |
37 |
Correct |
757 ms |
51544 KB |
Output is correct |
38 |
Correct |
681 ms |
39508 KB |
Output is correct |
39 |
Correct |
570 ms |
31316 KB |
Output is correct |
40 |
Correct |
552 ms |
23692 KB |
Output is correct |
41 |
Correct |
593 ms |
31228 KB |
Output is correct |
42 |
Correct |
567 ms |
23404 KB |
Output is correct |
43 |
Correct |
1606 ms |
10896 KB |
Output is correct |
44 |
Correct |
26 ms |
5844 KB |
Output is correct |
45 |
Correct |
169 ms |
6924 KB |
Output is correct |
46 |
Correct |
104 ms |
7084 KB |
Output is correct |
47 |
Correct |
1601 ms |
9720 KB |
Output is correct |
48 |
Correct |
1554 ms |
10872 KB |
Output is correct |
49 |
Correct |
1583 ms |
9856 KB |
Output is correct |
50 |
Correct |
735 ms |
8644 KB |
Output is correct |
51 |
Correct |
727 ms |
8692 KB |
Output is correct |
52 |
Correct |
737 ms |
9008 KB |
Output is correct |
53 |
Correct |
1176 ms |
9796 KB |
Output is correct |
54 |
Correct |
1168 ms |
9780 KB |
Output is correct |
55 |
Correct |
1168 ms |
10584 KB |
Output is correct |
56 |
Correct |
1367 ms |
10164 KB |
Output is correct |
57 |
Correct |
1480 ms |
10068 KB |
Output is correct |
58 |
Correct |
1640 ms |
10900 KB |
Output is correct |
59 |
Correct |
1608 ms |
10856 KB |
Output is correct |
60 |
Correct |
1579 ms |
11076 KB |
Output is correct |
61 |
Correct |
1566 ms |
10908 KB |
Output is correct |
62 |
Correct |
1367 ms |
10840 KB |
Output is correct |
63 |
Correct |
1340 ms |
10768 KB |
Output is correct |
64 |
Correct |
1531 ms |
11500 KB |
Output is correct |
65 |
Correct |
1418 ms |
9628 KB |
Output is correct |
66 |
Correct |
1051 ms |
59244 KB |
Output is correct |
67 |
Correct |
1151 ms |
84912 KB |
Output is correct |
68 |
Correct |
1106 ms |
58088 KB |
Output is correct |
69 |
Correct |
955 ms |
25420 KB |
Output is correct |
70 |
Correct |
1127 ms |
72688 KB |
Output is correct |
71 |
Correct |
1126 ms |
75192 KB |
Output is correct |
72 |
Correct |
1139 ms |
75652 KB |
Output is correct |
73 |
Correct |
1096 ms |
57600 KB |
Output is correct |
74 |
Correct |
1102 ms |
58112 KB |
Output is correct |
75 |
Correct |
1100 ms |
58208 KB |
Output is correct |
76 |
Correct |
992 ms |
30440 KB |
Output is correct |
77 |
Correct |
1004 ms |
29336 KB |
Output is correct |
78 |
Correct |
968 ms |
28160 KB |
Output is correct |
79 |
Correct |
812 ms |
17272 KB |
Output is correct |
80 |
Correct |
819 ms |
16688 KB |
Output is correct |
81 |
Correct |
814 ms |
16376 KB |
Output is correct |
82 |
Correct |
830 ms |
16208 KB |
Output is correct |
83 |
Correct |
832 ms |
15768 KB |
Output is correct |
84 |
Correct |
831 ms |
15436 KB |
Output is correct |
85 |
Correct |
1933 ms |
61648 KB |
Output is correct |
86 |
Correct |
203 ms |
11800 KB |
Output is correct |
87 |
Correct |
133 ms |
16656 KB |
Output is correct |
88 |
Correct |
1895 ms |
71260 KB |
Output is correct |
89 |
Correct |
1971 ms |
60892 KB |
Output is correct |
90 |
Correct |
1859 ms |
73208 KB |
Output is correct |
91 |
Correct |
1120 ms |
59256 KB |
Output is correct |
92 |
Correct |
1114 ms |
59284 KB |
Output is correct |
93 |
Correct |
1174 ms |
110068 KB |
Output is correct |
94 |
Correct |
1606 ms |
60564 KB |
Output is correct |
95 |
Correct |
1539 ms |
60552 KB |
Output is correct |
96 |
Correct |
1522 ms |
110544 KB |
Output is correct |
97 |
Correct |
1730 ms |
33744 KB |
Output is correct |
98 |
Correct |
1810 ms |
32328 KB |
Output is correct |
99 |
Correct |
1952 ms |
62744 KB |
Output is correct |
100 |
Correct |
1967 ms |
61644 KB |
Output is correct |
101 |
Correct |
2011 ms |
61504 KB |
Output is correct |
102 |
Correct |
1997 ms |
61516 KB |
Output is correct |
103 |
Correct |
1715 ms |
111112 KB |
Output is correct |
104 |
Correct |
1668 ms |
111020 KB |
Output is correct |
105 |
Correct |
1502 ms |
50264 KB |
Output is correct |
106 |
Correct |
1274 ms |
30144 KB |
Output is correct |
107 |
Correct |
1472 ms |
48700 KB |
Output is correct |
108 |
Correct |
1889 ms |
99692 KB |
Output is correct |
109 |
Correct |
1716 ms |
109568 KB |
Output is correct |