# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
476902 |
2021-09-29T02:29:17 Z |
dooompy |
Bridges (APIO19_bridges) |
C++17 |
|
2379 ms |
44144 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int B = 1000;
int n, m, q;
vector<pair<int, int>> adj[500005];
int u[500005], v[500005], d[500005];
int t[100005], x[100005], y[100005];
bool changed[100005];
vector<int> to_add[B];
stack<int> stck;
int sz[100001], cmp[100001];
int ans[100001];
void reset() {
iota(cmp + 1, cmp + 1 + n, 1);
fill(sz + 1, sz + n + 1, 1);
}
int find(int a) {
while (cmp[a] != a) a = cmp[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);
stck.push(a);
sz[b] += sz[a];
cmp[a] = cmp[b];
}
void rollback(int x) {
while (stck.size() > x) {
int k = stck.top();
stck.pop();
sz[cmp[k]] -= sz[k];
cmp[k] = k;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> d[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> t[i] >> x[i] >> y[i];
}
for (int l = 1; l <= q; l += B) {
int r = min(q + 1, l + B);
fill(changed + 1, changed + m + 1, false);
reset();
vector<int> ask, upd, unchanged;
for (int i = l; i < r; i++) {
if (t[i] == 1) {
changed[x[i]] = true;
upd.push_back(i);
} else {
ask.push_back(i);
}
}
for (int i = 1; i <= m; i++) {
if (!changed[i]) unchanged.push_back(i);
}
for (int i = l; i < r; i++) {
if (t[i] == 1) {
d[x[i]] = y[i];
} else {
to_add[i - l].clear();
for (auto a : upd) {
if (d[x[a]] >= y[i]) to_add[i - l].push_back(x[a]);
}
}
}
sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
sort(unchanged.begin(), unchanged.end(), [&](int a, int b) { return d[a] > d[b]; });
int ptr = 0;
for (int i : ask) {
while (ptr < unchanged.size() && d[unchanged[ptr]] >= y[i]) {
onion(v[unchanged[ptr]], u[unchanged[ptr]]);
ptr++;
}
int now = stck.size();
for (auto a : to_add[i - l]) {
onion(v[a], u[a]);
}
ans[i] = sz[find(x[i])];
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:41:24: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | while (stck.size() > x) {
| ~~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while (ptr < unchanged.size() && d[unchanged[ptr]] >= y[i]) {
| ~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12108 KB |
Output is correct |
2 |
Correct |
7 ms |
12108 KB |
Output is correct |
3 |
Correct |
45 ms |
14536 KB |
Output is correct |
4 |
Correct |
10 ms |
12436 KB |
Output is correct |
5 |
Correct |
46 ms |
14760 KB |
Output is correct |
6 |
Correct |
35 ms |
14460 KB |
Output is correct |
7 |
Correct |
42 ms |
15380 KB |
Output is correct |
8 |
Correct |
48 ms |
14480 KB |
Output is correct |
9 |
Correct |
54 ms |
16036 KB |
Output is correct |
10 |
Correct |
46 ms |
14636 KB |
Output is correct |
11 |
Correct |
49 ms |
14532 KB |
Output is correct |
12 |
Correct |
61 ms |
14660 KB |
Output is correct |
13 |
Correct |
54 ms |
14624 KB |
Output is correct |
14 |
Correct |
51 ms |
14572 KB |
Output is correct |
15 |
Correct |
70 ms |
14548 KB |
Output is correct |
16 |
Correct |
48 ms |
15684 KB |
Output is correct |
17 |
Correct |
52 ms |
15252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1440 ms |
37752 KB |
Output is correct |
2 |
Correct |
1494 ms |
40704 KB |
Output is correct |
3 |
Correct |
1523 ms |
40656 KB |
Output is correct |
4 |
Correct |
1550 ms |
40548 KB |
Output is correct |
5 |
Correct |
1495 ms |
40852 KB |
Output is correct |
6 |
Correct |
2224 ms |
42216 KB |
Output is correct |
7 |
Correct |
2268 ms |
42328 KB |
Output is correct |
8 |
Correct |
2281 ms |
42256 KB |
Output is correct |
9 |
Correct |
46 ms |
15172 KB |
Output is correct |
10 |
Correct |
1305 ms |
41336 KB |
Output is correct |
11 |
Correct |
1191 ms |
41472 KB |
Output is correct |
12 |
Correct |
1292 ms |
38888 KB |
Output is correct |
13 |
Correct |
1342 ms |
42112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1188 ms |
30564 KB |
Output is correct |
2 |
Correct |
922 ms |
22972 KB |
Output is correct |
3 |
Correct |
1411 ms |
34512 KB |
Output is correct |
4 |
Correct |
1163 ms |
32984 KB |
Output is correct |
5 |
Correct |
50 ms |
15300 KB |
Output is correct |
6 |
Correct |
1307 ms |
32788 KB |
Output is correct |
7 |
Correct |
1014 ms |
32600 KB |
Output is correct |
8 |
Correct |
886 ms |
32280 KB |
Output is correct |
9 |
Correct |
772 ms |
31144 KB |
Output is correct |
10 |
Correct |
668 ms |
31084 KB |
Output is correct |
11 |
Correct |
773 ms |
33888 KB |
Output is correct |
12 |
Correct |
685 ms |
33912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1738 ms |
36552 KB |
Output is correct |
2 |
Correct |
47 ms |
15196 KB |
Output is correct |
3 |
Correct |
187 ms |
16300 KB |
Output is correct |
4 |
Correct |
94 ms |
16456 KB |
Output is correct |
5 |
Correct |
819 ms |
38908 KB |
Output is correct |
6 |
Correct |
1716 ms |
40520 KB |
Output is correct |
7 |
Correct |
894 ms |
38952 KB |
Output is correct |
8 |
Correct |
840 ms |
38292 KB |
Output is correct |
9 |
Correct |
826 ms |
38600 KB |
Output is correct |
10 |
Correct |
893 ms |
38488 KB |
Output is correct |
11 |
Correct |
1260 ms |
39644 KB |
Output is correct |
12 |
Correct |
1229 ms |
39780 KB |
Output is correct |
13 |
Correct |
1259 ms |
39924 KB |
Output is correct |
14 |
Correct |
809 ms |
38920 KB |
Output is correct |
15 |
Correct |
820 ms |
38876 KB |
Output is correct |
16 |
Correct |
1673 ms |
40644 KB |
Output is correct |
17 |
Correct |
1769 ms |
40568 KB |
Output is correct |
18 |
Correct |
1653 ms |
41068 KB |
Output is correct |
19 |
Correct |
1688 ms |
40904 KB |
Output is correct |
20 |
Correct |
1415 ms |
40088 KB |
Output is correct |
21 |
Correct |
1413 ms |
40172 KB |
Output is correct |
22 |
Correct |
1607 ms |
40200 KB |
Output is correct |
23 |
Correct |
923 ms |
36776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1440 ms |
37752 KB |
Output is correct |
2 |
Correct |
1494 ms |
40704 KB |
Output is correct |
3 |
Correct |
1523 ms |
40656 KB |
Output is correct |
4 |
Correct |
1550 ms |
40548 KB |
Output is correct |
5 |
Correct |
1495 ms |
40852 KB |
Output is correct |
6 |
Correct |
2224 ms |
42216 KB |
Output is correct |
7 |
Correct |
2268 ms |
42328 KB |
Output is correct |
8 |
Correct |
2281 ms |
42256 KB |
Output is correct |
9 |
Correct |
46 ms |
15172 KB |
Output is correct |
10 |
Correct |
1305 ms |
41336 KB |
Output is correct |
11 |
Correct |
1191 ms |
41472 KB |
Output is correct |
12 |
Correct |
1292 ms |
38888 KB |
Output is correct |
13 |
Correct |
1342 ms |
42112 KB |
Output is correct |
14 |
Correct |
1188 ms |
30564 KB |
Output is correct |
15 |
Correct |
922 ms |
22972 KB |
Output is correct |
16 |
Correct |
1411 ms |
34512 KB |
Output is correct |
17 |
Correct |
1163 ms |
32984 KB |
Output is correct |
18 |
Correct |
50 ms |
15300 KB |
Output is correct |
19 |
Correct |
1307 ms |
32788 KB |
Output is correct |
20 |
Correct |
1014 ms |
32600 KB |
Output is correct |
21 |
Correct |
886 ms |
32280 KB |
Output is correct |
22 |
Correct |
772 ms |
31144 KB |
Output is correct |
23 |
Correct |
668 ms |
31084 KB |
Output is correct |
24 |
Correct |
773 ms |
33888 KB |
Output is correct |
25 |
Correct |
685 ms |
33912 KB |
Output is correct |
26 |
Correct |
1432 ms |
40880 KB |
Output is correct |
27 |
Correct |
1881 ms |
42328 KB |
Output is correct |
28 |
Correct |
1634 ms |
40676 KB |
Output is correct |
29 |
Correct |
1089 ms |
40216 KB |
Output is correct |
30 |
Correct |
1815 ms |
42136 KB |
Output is correct |
31 |
Correct |
1863 ms |
42336 KB |
Output is correct |
32 |
Correct |
1843 ms |
42384 KB |
Output is correct |
33 |
Correct |
1530 ms |
40608 KB |
Output is correct |
34 |
Correct |
1519 ms |
40656 KB |
Output is correct |
35 |
Correct |
1521 ms |
40660 KB |
Output is correct |
36 |
Correct |
1171 ms |
40320 KB |
Output is correct |
37 |
Correct |
1116 ms |
40208 KB |
Output is correct |
38 |
Correct |
1105 ms |
40300 KB |
Output is correct |
39 |
Correct |
919 ms |
38960 KB |
Output is correct |
40 |
Correct |
907 ms |
38860 KB |
Output is correct |
41 |
Correct |
927 ms |
38796 KB |
Output is correct |
42 |
Correct |
901 ms |
40924 KB |
Output is correct |
43 |
Correct |
913 ms |
40868 KB |
Output is correct |
44 |
Correct |
891 ms |
40744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12108 KB |
Output is correct |
2 |
Correct |
7 ms |
12108 KB |
Output is correct |
3 |
Correct |
45 ms |
14536 KB |
Output is correct |
4 |
Correct |
10 ms |
12436 KB |
Output is correct |
5 |
Correct |
46 ms |
14760 KB |
Output is correct |
6 |
Correct |
35 ms |
14460 KB |
Output is correct |
7 |
Correct |
42 ms |
15380 KB |
Output is correct |
8 |
Correct |
48 ms |
14480 KB |
Output is correct |
9 |
Correct |
54 ms |
16036 KB |
Output is correct |
10 |
Correct |
46 ms |
14636 KB |
Output is correct |
11 |
Correct |
49 ms |
14532 KB |
Output is correct |
12 |
Correct |
61 ms |
14660 KB |
Output is correct |
13 |
Correct |
54 ms |
14624 KB |
Output is correct |
14 |
Correct |
51 ms |
14572 KB |
Output is correct |
15 |
Correct |
70 ms |
14548 KB |
Output is correct |
16 |
Correct |
48 ms |
15684 KB |
Output is correct |
17 |
Correct |
52 ms |
15252 KB |
Output is correct |
18 |
Correct |
1440 ms |
37752 KB |
Output is correct |
19 |
Correct |
1494 ms |
40704 KB |
Output is correct |
20 |
Correct |
1523 ms |
40656 KB |
Output is correct |
21 |
Correct |
1550 ms |
40548 KB |
Output is correct |
22 |
Correct |
1495 ms |
40852 KB |
Output is correct |
23 |
Correct |
2224 ms |
42216 KB |
Output is correct |
24 |
Correct |
2268 ms |
42328 KB |
Output is correct |
25 |
Correct |
2281 ms |
42256 KB |
Output is correct |
26 |
Correct |
46 ms |
15172 KB |
Output is correct |
27 |
Correct |
1305 ms |
41336 KB |
Output is correct |
28 |
Correct |
1191 ms |
41472 KB |
Output is correct |
29 |
Correct |
1292 ms |
38888 KB |
Output is correct |
30 |
Correct |
1342 ms |
42112 KB |
Output is correct |
31 |
Correct |
1188 ms |
30564 KB |
Output is correct |
32 |
Correct |
922 ms |
22972 KB |
Output is correct |
33 |
Correct |
1411 ms |
34512 KB |
Output is correct |
34 |
Correct |
1163 ms |
32984 KB |
Output is correct |
35 |
Correct |
50 ms |
15300 KB |
Output is correct |
36 |
Correct |
1307 ms |
32788 KB |
Output is correct |
37 |
Correct |
1014 ms |
32600 KB |
Output is correct |
38 |
Correct |
886 ms |
32280 KB |
Output is correct |
39 |
Correct |
772 ms |
31144 KB |
Output is correct |
40 |
Correct |
668 ms |
31084 KB |
Output is correct |
41 |
Correct |
773 ms |
33888 KB |
Output is correct |
42 |
Correct |
685 ms |
33912 KB |
Output is correct |
43 |
Correct |
1738 ms |
36552 KB |
Output is correct |
44 |
Correct |
47 ms |
15196 KB |
Output is correct |
45 |
Correct |
187 ms |
16300 KB |
Output is correct |
46 |
Correct |
94 ms |
16456 KB |
Output is correct |
47 |
Correct |
819 ms |
38908 KB |
Output is correct |
48 |
Correct |
1716 ms |
40520 KB |
Output is correct |
49 |
Correct |
894 ms |
38952 KB |
Output is correct |
50 |
Correct |
840 ms |
38292 KB |
Output is correct |
51 |
Correct |
826 ms |
38600 KB |
Output is correct |
52 |
Correct |
893 ms |
38488 KB |
Output is correct |
53 |
Correct |
1260 ms |
39644 KB |
Output is correct |
54 |
Correct |
1229 ms |
39780 KB |
Output is correct |
55 |
Correct |
1259 ms |
39924 KB |
Output is correct |
56 |
Correct |
809 ms |
38920 KB |
Output is correct |
57 |
Correct |
820 ms |
38876 KB |
Output is correct |
58 |
Correct |
1673 ms |
40644 KB |
Output is correct |
59 |
Correct |
1769 ms |
40568 KB |
Output is correct |
60 |
Correct |
1653 ms |
41068 KB |
Output is correct |
61 |
Correct |
1688 ms |
40904 KB |
Output is correct |
62 |
Correct |
1415 ms |
40088 KB |
Output is correct |
63 |
Correct |
1413 ms |
40172 KB |
Output is correct |
64 |
Correct |
1607 ms |
40200 KB |
Output is correct |
65 |
Correct |
923 ms |
36776 KB |
Output is correct |
66 |
Correct |
1432 ms |
40880 KB |
Output is correct |
67 |
Correct |
1881 ms |
42328 KB |
Output is correct |
68 |
Correct |
1634 ms |
40676 KB |
Output is correct |
69 |
Correct |
1089 ms |
40216 KB |
Output is correct |
70 |
Correct |
1815 ms |
42136 KB |
Output is correct |
71 |
Correct |
1863 ms |
42336 KB |
Output is correct |
72 |
Correct |
1843 ms |
42384 KB |
Output is correct |
73 |
Correct |
1530 ms |
40608 KB |
Output is correct |
74 |
Correct |
1519 ms |
40656 KB |
Output is correct |
75 |
Correct |
1521 ms |
40660 KB |
Output is correct |
76 |
Correct |
1171 ms |
40320 KB |
Output is correct |
77 |
Correct |
1116 ms |
40208 KB |
Output is correct |
78 |
Correct |
1105 ms |
40300 KB |
Output is correct |
79 |
Correct |
919 ms |
38960 KB |
Output is correct |
80 |
Correct |
907 ms |
38860 KB |
Output is correct |
81 |
Correct |
927 ms |
38796 KB |
Output is correct |
82 |
Correct |
901 ms |
40924 KB |
Output is correct |
83 |
Correct |
913 ms |
40868 KB |
Output is correct |
84 |
Correct |
891 ms |
40744 KB |
Output is correct |
85 |
Correct |
2123 ms |
42560 KB |
Output is correct |
86 |
Correct |
217 ms |
18360 KB |
Output is correct |
87 |
Correct |
149 ms |
19784 KB |
Output is correct |
88 |
Correct |
1271 ms |
42856 KB |
Output is correct |
89 |
Correct |
2113 ms |
42816 KB |
Output is correct |
90 |
Correct |
1353 ms |
42912 KB |
Output is correct |
91 |
Correct |
1626 ms |
40620 KB |
Output is correct |
92 |
Correct |
1549 ms |
40476 KB |
Output is correct |
93 |
Correct |
2318 ms |
41904 KB |
Output is correct |
94 |
Correct |
1861 ms |
42124 KB |
Output is correct |
95 |
Correct |
1846 ms |
42188 KB |
Output is correct |
96 |
Correct |
2156 ms |
43980 KB |
Output is correct |
97 |
Correct |
1006 ms |
39540 KB |
Output is correct |
98 |
Correct |
1093 ms |
42556 KB |
Output is correct |
99 |
Correct |
2152 ms |
42984 KB |
Output is correct |
100 |
Correct |
2184 ms |
42924 KB |
Output is correct |
101 |
Correct |
2322 ms |
43108 KB |
Output is correct |
102 |
Correct |
2211 ms |
43176 KB |
Output is correct |
103 |
Correct |
2354 ms |
44100 KB |
Output is correct |
104 |
Correct |
2379 ms |
44144 KB |
Output is correct |
105 |
Correct |
1748 ms |
43780 KB |
Output is correct |
106 |
Correct |
1406 ms |
43516 KB |
Output is correct |
107 |
Correct |
1693 ms |
40780 KB |
Output is correct |
108 |
Correct |
2195 ms |
42956 KB |
Output is correct |
109 |
Correct |
1629 ms |
40688 KB |
Output is correct |