# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
490317 |
2021-11-27T01:16:42 Z |
dooompy |
Bridges (APIO19_bridges) |
C++17 |
|
1948 ms |
32568 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int B = 1000;
int u[100005], v[100005], d[100005];
int t[100005], a[100005], b[100005];
vector<int> to_add[1005];
int par[100005], sz[100005];
int ans[100005];
stack<int> st;
void reset() {
iota(par + 1, par + 100001, 1);
fill(sz, sz + 100005, 1);
}
int find(int a) {
while (a != par[a]) a = par[a];
return a;
}
void onion(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
sz[a] += sz[b];
par[b] = par[a];
st.push(b);
}
void rollback(int s) {
while (st.size() > s) {
int k = st.top();
st.pop();
sz[par[k]] -= sz[k];
par[k] = k;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n, m; cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> d[i];
}
int q; cin >> q;
for (int i = 1; i <= q; i++) {
cin >> t[i] >> a[i] >> b[i];
}
for (int l = 1; l <= q; l += B) {
int r = min(l + B, q + 1);
reset();
vector<int> ask, update, unchanged;
vector<bool> changes(100005);
for (int i = l; i < r; i++) {
if (t[i] == 2) {
// ask
ask.push_back(i);
} else {
// change
update.push_back(i);
changes[a[i]] = true;
}
}
for (int i = 1; i <= m; i++) {
if (!changes[i]) {
unchanged.push_back(i);
}
}
for (int i = l; i < r; i++) {
if (t[i] == 1) {
d[a[i]] = b[i];
} else {
to_add[i-l].clear();
for (auto x : update) {
if (d[a[x]] >= b[i]) {
to_add[i - l].push_back(a[x]);
}
}
}
}
sort(ask.begin(), ask.end(), [](int x, int y) {
return b[x] > b[y];
});
sort(unchanged.begin(), unchanged.end(), [](int x, int y) {
return d[x] > d[y];
});
int ptr = 0;
for (int j : ask) {
while (ptr < unchanged.size() && d[unchanged[ptr]] >= b[j]) {
onion(u[unchanged[ptr]], v[unchanged[ptr]]);
ptr++;
}
int now = st.size();
for (auto a : to_add[j - l]) {
onion(v[a], u[a]);
}
ans[j] = sz[find(a[j])];
rollback(now);
}
}
for (int i = 1; i <= q; i++) {
if (t[i] == 2) cout << ans[i] << "\n";
}
}
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:36:22: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | while (st.size() > s) {
| ~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | while (ptr < unchanged.size() && d[unchanged[ptr]] >= b[j]) {
| ~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1100 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
35 ms |
3656 KB |
Output is correct |
4 |
Correct |
5 ms |
1484 KB |
Output is correct |
5 |
Correct |
36 ms |
3756 KB |
Output is correct |
6 |
Correct |
26 ms |
3492 KB |
Output is correct |
7 |
Correct |
32 ms |
4376 KB |
Output is correct |
8 |
Correct |
36 ms |
3556 KB |
Output is correct |
9 |
Correct |
43 ms |
5056 KB |
Output is correct |
10 |
Correct |
37 ms |
3668 KB |
Output is correct |
11 |
Correct |
37 ms |
3572 KB |
Output is correct |
12 |
Correct |
43 ms |
3676 KB |
Output is correct |
13 |
Correct |
49 ms |
3684 KB |
Output is correct |
14 |
Correct |
40 ms |
3532 KB |
Output is correct |
15 |
Correct |
42 ms |
3516 KB |
Output is correct |
16 |
Correct |
41 ms |
4804 KB |
Output is correct |
17 |
Correct |
39 ms |
4228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1244 ms |
26488 KB |
Output is correct |
2 |
Correct |
1271 ms |
29128 KB |
Output is correct |
3 |
Correct |
1216 ms |
29256 KB |
Output is correct |
4 |
Correct |
1293 ms |
29224 KB |
Output is correct |
5 |
Correct |
1279 ms |
29432 KB |
Output is correct |
6 |
Correct |
1939 ms |
30776 KB |
Output is correct |
7 |
Correct |
1859 ms |
30784 KB |
Output is correct |
8 |
Correct |
1885 ms |
30892 KB |
Output is correct |
9 |
Correct |
42 ms |
4164 KB |
Output is correct |
10 |
Correct |
1099 ms |
29848 KB |
Output is correct |
11 |
Correct |
1026 ms |
29804 KB |
Output is correct |
12 |
Correct |
1065 ms |
27576 KB |
Output is correct |
13 |
Correct |
1081 ms |
30564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
979 ms |
19132 KB |
Output is correct |
2 |
Correct |
771 ms |
11972 KB |
Output is correct |
3 |
Correct |
1186 ms |
23204 KB |
Output is correct |
4 |
Correct |
973 ms |
21644 KB |
Output is correct |
5 |
Correct |
45 ms |
4220 KB |
Output is correct |
6 |
Correct |
1103 ms |
21540 KB |
Output is correct |
7 |
Correct |
893 ms |
21300 KB |
Output is correct |
8 |
Correct |
785 ms |
21092 KB |
Output is correct |
9 |
Correct |
646 ms |
19888 KB |
Output is correct |
10 |
Correct |
572 ms |
19776 KB |
Output is correct |
11 |
Correct |
686 ms |
22720 KB |
Output is correct |
12 |
Correct |
587 ms |
22500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1414 ms |
25184 KB |
Output is correct |
2 |
Correct |
40 ms |
4216 KB |
Output is correct |
3 |
Correct |
144 ms |
5180 KB |
Output is correct |
4 |
Correct |
68 ms |
5352 KB |
Output is correct |
5 |
Correct |
710 ms |
27652 KB |
Output is correct |
6 |
Correct |
1349 ms |
28952 KB |
Output is correct |
7 |
Correct |
718 ms |
27504 KB |
Output is correct |
8 |
Correct |
713 ms |
27008 KB |
Output is correct |
9 |
Correct |
698 ms |
27092 KB |
Output is correct |
10 |
Correct |
709 ms |
27068 KB |
Output is correct |
11 |
Correct |
1057 ms |
28188 KB |
Output is correct |
12 |
Correct |
1033 ms |
28332 KB |
Output is correct |
13 |
Correct |
1024 ms |
28288 KB |
Output is correct |
14 |
Correct |
614 ms |
27520 KB |
Output is correct |
15 |
Correct |
656 ms |
27424 KB |
Output is correct |
16 |
Correct |
1372 ms |
29240 KB |
Output is correct |
17 |
Correct |
1375 ms |
29180 KB |
Output is correct |
18 |
Correct |
1342 ms |
29612 KB |
Output is correct |
19 |
Correct |
1378 ms |
29516 KB |
Output is correct |
20 |
Correct |
1155 ms |
28696 KB |
Output is correct |
21 |
Correct |
1145 ms |
28580 KB |
Output is correct |
22 |
Correct |
1337 ms |
28580 KB |
Output is correct |
23 |
Correct |
761 ms |
25300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1244 ms |
26488 KB |
Output is correct |
2 |
Correct |
1271 ms |
29128 KB |
Output is correct |
3 |
Correct |
1216 ms |
29256 KB |
Output is correct |
4 |
Correct |
1293 ms |
29224 KB |
Output is correct |
5 |
Correct |
1279 ms |
29432 KB |
Output is correct |
6 |
Correct |
1939 ms |
30776 KB |
Output is correct |
7 |
Correct |
1859 ms |
30784 KB |
Output is correct |
8 |
Correct |
1885 ms |
30892 KB |
Output is correct |
9 |
Correct |
42 ms |
4164 KB |
Output is correct |
10 |
Correct |
1099 ms |
29848 KB |
Output is correct |
11 |
Correct |
1026 ms |
29804 KB |
Output is correct |
12 |
Correct |
1065 ms |
27576 KB |
Output is correct |
13 |
Correct |
1081 ms |
30564 KB |
Output is correct |
14 |
Correct |
979 ms |
19132 KB |
Output is correct |
15 |
Correct |
771 ms |
11972 KB |
Output is correct |
16 |
Correct |
1186 ms |
23204 KB |
Output is correct |
17 |
Correct |
973 ms |
21644 KB |
Output is correct |
18 |
Correct |
45 ms |
4220 KB |
Output is correct |
19 |
Correct |
1103 ms |
21540 KB |
Output is correct |
20 |
Correct |
893 ms |
21300 KB |
Output is correct |
21 |
Correct |
785 ms |
21092 KB |
Output is correct |
22 |
Correct |
646 ms |
19888 KB |
Output is correct |
23 |
Correct |
572 ms |
19776 KB |
Output is correct |
24 |
Correct |
686 ms |
22720 KB |
Output is correct |
25 |
Correct |
587 ms |
22500 KB |
Output is correct |
26 |
Correct |
1229 ms |
29500 KB |
Output is correct |
27 |
Correct |
1591 ms |
30864 KB |
Output is correct |
28 |
Correct |
1300 ms |
29336 KB |
Output is correct |
29 |
Correct |
930 ms |
28876 KB |
Output is correct |
30 |
Correct |
1496 ms |
30868 KB |
Output is correct |
31 |
Correct |
1498 ms |
30728 KB |
Output is correct |
32 |
Correct |
1579 ms |
31036 KB |
Output is correct |
33 |
Correct |
1292 ms |
29128 KB |
Output is correct |
34 |
Correct |
1308 ms |
29052 KB |
Output is correct |
35 |
Correct |
1303 ms |
29216 KB |
Output is correct |
36 |
Correct |
976 ms |
28972 KB |
Output is correct |
37 |
Correct |
958 ms |
28812 KB |
Output is correct |
38 |
Correct |
955 ms |
28824 KB |
Output is correct |
39 |
Correct |
787 ms |
27388 KB |
Output is correct |
40 |
Correct |
775 ms |
27484 KB |
Output is correct |
41 |
Correct |
777 ms |
27416 KB |
Output is correct |
42 |
Correct |
779 ms |
29476 KB |
Output is correct |
43 |
Correct |
771 ms |
29344 KB |
Output is correct |
44 |
Correct |
766 ms |
29320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1100 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
35 ms |
3656 KB |
Output is correct |
4 |
Correct |
5 ms |
1484 KB |
Output is correct |
5 |
Correct |
36 ms |
3756 KB |
Output is correct |
6 |
Correct |
26 ms |
3492 KB |
Output is correct |
7 |
Correct |
32 ms |
4376 KB |
Output is correct |
8 |
Correct |
36 ms |
3556 KB |
Output is correct |
9 |
Correct |
43 ms |
5056 KB |
Output is correct |
10 |
Correct |
37 ms |
3668 KB |
Output is correct |
11 |
Correct |
37 ms |
3572 KB |
Output is correct |
12 |
Correct |
43 ms |
3676 KB |
Output is correct |
13 |
Correct |
49 ms |
3684 KB |
Output is correct |
14 |
Correct |
40 ms |
3532 KB |
Output is correct |
15 |
Correct |
42 ms |
3516 KB |
Output is correct |
16 |
Correct |
41 ms |
4804 KB |
Output is correct |
17 |
Correct |
39 ms |
4228 KB |
Output is correct |
18 |
Correct |
1244 ms |
26488 KB |
Output is correct |
19 |
Correct |
1271 ms |
29128 KB |
Output is correct |
20 |
Correct |
1216 ms |
29256 KB |
Output is correct |
21 |
Correct |
1293 ms |
29224 KB |
Output is correct |
22 |
Correct |
1279 ms |
29432 KB |
Output is correct |
23 |
Correct |
1939 ms |
30776 KB |
Output is correct |
24 |
Correct |
1859 ms |
30784 KB |
Output is correct |
25 |
Correct |
1885 ms |
30892 KB |
Output is correct |
26 |
Correct |
42 ms |
4164 KB |
Output is correct |
27 |
Correct |
1099 ms |
29848 KB |
Output is correct |
28 |
Correct |
1026 ms |
29804 KB |
Output is correct |
29 |
Correct |
1065 ms |
27576 KB |
Output is correct |
30 |
Correct |
1081 ms |
30564 KB |
Output is correct |
31 |
Correct |
979 ms |
19132 KB |
Output is correct |
32 |
Correct |
771 ms |
11972 KB |
Output is correct |
33 |
Correct |
1186 ms |
23204 KB |
Output is correct |
34 |
Correct |
973 ms |
21644 KB |
Output is correct |
35 |
Correct |
45 ms |
4220 KB |
Output is correct |
36 |
Correct |
1103 ms |
21540 KB |
Output is correct |
37 |
Correct |
893 ms |
21300 KB |
Output is correct |
38 |
Correct |
785 ms |
21092 KB |
Output is correct |
39 |
Correct |
646 ms |
19888 KB |
Output is correct |
40 |
Correct |
572 ms |
19776 KB |
Output is correct |
41 |
Correct |
686 ms |
22720 KB |
Output is correct |
42 |
Correct |
587 ms |
22500 KB |
Output is correct |
43 |
Correct |
1414 ms |
25184 KB |
Output is correct |
44 |
Correct |
40 ms |
4216 KB |
Output is correct |
45 |
Correct |
144 ms |
5180 KB |
Output is correct |
46 |
Correct |
68 ms |
5352 KB |
Output is correct |
47 |
Correct |
710 ms |
27652 KB |
Output is correct |
48 |
Correct |
1349 ms |
28952 KB |
Output is correct |
49 |
Correct |
718 ms |
27504 KB |
Output is correct |
50 |
Correct |
713 ms |
27008 KB |
Output is correct |
51 |
Correct |
698 ms |
27092 KB |
Output is correct |
52 |
Correct |
709 ms |
27068 KB |
Output is correct |
53 |
Correct |
1057 ms |
28188 KB |
Output is correct |
54 |
Correct |
1033 ms |
28332 KB |
Output is correct |
55 |
Correct |
1024 ms |
28288 KB |
Output is correct |
56 |
Correct |
614 ms |
27520 KB |
Output is correct |
57 |
Correct |
656 ms |
27424 KB |
Output is correct |
58 |
Correct |
1372 ms |
29240 KB |
Output is correct |
59 |
Correct |
1375 ms |
29180 KB |
Output is correct |
60 |
Correct |
1342 ms |
29612 KB |
Output is correct |
61 |
Correct |
1378 ms |
29516 KB |
Output is correct |
62 |
Correct |
1155 ms |
28696 KB |
Output is correct |
63 |
Correct |
1145 ms |
28580 KB |
Output is correct |
64 |
Correct |
1337 ms |
28580 KB |
Output is correct |
65 |
Correct |
761 ms |
25300 KB |
Output is correct |
66 |
Correct |
1229 ms |
29500 KB |
Output is correct |
67 |
Correct |
1591 ms |
30864 KB |
Output is correct |
68 |
Correct |
1300 ms |
29336 KB |
Output is correct |
69 |
Correct |
930 ms |
28876 KB |
Output is correct |
70 |
Correct |
1496 ms |
30868 KB |
Output is correct |
71 |
Correct |
1498 ms |
30728 KB |
Output is correct |
72 |
Correct |
1579 ms |
31036 KB |
Output is correct |
73 |
Correct |
1292 ms |
29128 KB |
Output is correct |
74 |
Correct |
1308 ms |
29052 KB |
Output is correct |
75 |
Correct |
1303 ms |
29216 KB |
Output is correct |
76 |
Correct |
976 ms |
28972 KB |
Output is correct |
77 |
Correct |
958 ms |
28812 KB |
Output is correct |
78 |
Correct |
955 ms |
28824 KB |
Output is correct |
79 |
Correct |
787 ms |
27388 KB |
Output is correct |
80 |
Correct |
775 ms |
27484 KB |
Output is correct |
81 |
Correct |
777 ms |
27416 KB |
Output is correct |
82 |
Correct |
779 ms |
29476 KB |
Output is correct |
83 |
Correct |
771 ms |
29344 KB |
Output is correct |
84 |
Correct |
766 ms |
29320 KB |
Output is correct |
85 |
Correct |
1765 ms |
31308 KB |
Output is correct |
86 |
Correct |
168 ms |
7204 KB |
Output is correct |
87 |
Correct |
113 ms |
8600 KB |
Output is correct |
88 |
Correct |
1065 ms |
31492 KB |
Output is correct |
89 |
Correct |
1760 ms |
31304 KB |
Output is correct |
90 |
Correct |
1062 ms |
31460 KB |
Output is correct |
91 |
Correct |
1300 ms |
29124 KB |
Output is correct |
92 |
Correct |
1317 ms |
29060 KB |
Output is correct |
93 |
Correct |
1937 ms |
30548 KB |
Output is correct |
94 |
Correct |
1510 ms |
30880 KB |
Output is correct |
95 |
Correct |
1502 ms |
30708 KB |
Output is correct |
96 |
Correct |
1728 ms |
32348 KB |
Output is correct |
97 |
Correct |
798 ms |
27992 KB |
Output is correct |
98 |
Correct |
860 ms |
31112 KB |
Output is correct |
99 |
Correct |
1785 ms |
31728 KB |
Output is correct |
100 |
Correct |
1780 ms |
31328 KB |
Output is correct |
101 |
Correct |
1845 ms |
31580 KB |
Output is correct |
102 |
Correct |
1809 ms |
31716 KB |
Output is correct |
103 |
Correct |
1946 ms |
32560 KB |
Output is correct |
104 |
Correct |
1948 ms |
32568 KB |
Output is correct |
105 |
Correct |
1478 ms |
32452 KB |
Output is correct |
106 |
Correct |
1211 ms |
31924 KB |
Output is correct |
107 |
Correct |
1363 ms |
29160 KB |
Output is correct |
108 |
Correct |
1825 ms |
31408 KB |
Output is correct |
109 |
Correct |
1313 ms |
29236 KB |
Output is correct |