# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
376915 |
2021-03-12T07:02:54 Z |
KoD |
Bridges (APIO19_bridges) |
C++17 |
|
2314 ms |
4552 KB |
#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct DSU {
Vec<int> par;
std::stack<std::pair<int, int>> past;
DSU(const int n): par(n, -1) { }
int find(int u) const {
while (par[u] >= 0) {
u = par[u];
}
return u;
}
int find_notrack(const int u) {
return par[u] < 0 ? u : par[u] = find_notrack(par[u]);
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return 0;
}
if (par[x] > par[y]) {
std::swap(x, y);
}
past.emplace(x, par[x]);
past.emplace(y, par[y]);
par[x] += par[y];
par[y] = x;
return 2;
}
void merge_notrack(int x, int y) {
x = find_notrack(x);
y = find_notrack(y);
if (x == y) {
return;
}
if (par[x] > par[y]) {
std::swap(x, y);
}
par[x] += par[y];
par[y] = x;
}
int comp(const int x) const {
return -par[find(x)];
}
void rollback() {
while (!past.empty()) {
const auto [i, v] = past.top();
past.pop();
par[i] = v;
}
}
};
int scan() {
int x;
std::scanf("%d", &x);
return x;
}
constexpr int BSIZE = 800;
int main() {
const auto N = scan();
const auto M = scan();
Vec<int> U(M), V(M), D(M);
for (int i = 0; i < M; ++i) {
U[i] = scan() - 1;
V[i] = scan() - 1;
D[i] = scan();
}
const auto Q = scan();
Vec<int> T(Q), K(Q), W(Q);
for (int i = 0; i < Q; ++i) {
T[i] = scan();
K[i] = scan() - 1;
W[i] = scan();
}
const auto Steps = (Q + BSIZE - 1) / BSIZE;
Vec<int> ans;
ans.reserve(Q);
Vec<bool> dyn(M);
Vec<int> still(M);
std::iota(still.begin(), still.end(), 0);
for (int step = 0; step < Steps; ++step) {
const auto qL = step * BSIZE;
const auto qR = std::min((step + 1) * BSIZE, Q);
Vec<int> set;
Vec<std::pair<int, int>> ask;
set.reserve(qR - qL);
ask.reserve(qR - qL);
for (int i = qL; i < qR; ++i) {
if (T[i] == 1) {
set.push_back(i);
dyn[K[i]] = true;
}
else {
ask.emplace_back(i, (int) ans.size());
ans.push_back(0);
}
}
std::sort(ask.begin(), ask.end(), [&](const auto &q1, const auto &q2) {
return W[q1.first] > W[q2.first];
});
Vec<int> change;
change.reserve(qR - qL);
for (int i = 0; i < M; ++i) {
if (dyn[i]) {
change.push_back(i);
}
}
std::sort(still.begin(), still.end(), [&](const int i, const int j) {
return D[i] < D[j];
});
DSU dsu(N);
int still_idx = (int) still.size();
for (const auto [idx, ptr]: ask) {
while (still_idx > 0) {
const auto i = still[still_idx - 1];
if (dyn[i]) {
still_idx -= 1;
continue;
}
if (W[idx] > D[i]) {
break;
}
still_idx -= 1;
dsu.merge_notrack(U[i], V[i]);
}
std::stack<std::pair<int, int>> past;
for (const auto i: set) {
if (i > idx) {
break;
}
past.emplace(K[i], D[K[i]]);
D[K[i]] = W[i];
}
for (const auto i: change) {
if (W[idx] <= D[i]) {
dsu.merge(U[i], V[i]);
}
}
ans[ptr] = dsu.comp(K[idx]);
dsu.rollback();
while (!past.empty()) {
const auto [i, v] = past.top();
past.pop();
D[i] = v;
}
}
for (const auto i: set) {
D[K[i]] = W[i];
dyn[K[i]] = false;
}
}
for (const auto x: ans) {
std::printf("%d\n", x);
}
return 0;
}
Compilation message
bridges.cpp: In function 'int scan()':
bridges.cpp:60:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | std::scanf("%d", &x);
| ~~~~~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
31 ms |
492 KB |
Output is correct |
4 |
Correct |
6 ms |
620 KB |
Output is correct |
5 |
Correct |
25 ms |
492 KB |
Output is correct |
6 |
Correct |
23 ms |
492 KB |
Output is correct |
7 |
Correct |
28 ms |
492 KB |
Output is correct |
8 |
Correct |
33 ms |
492 KB |
Output is correct |
9 |
Correct |
33 ms |
492 KB |
Output is correct |
10 |
Correct |
30 ms |
492 KB |
Output is correct |
11 |
Correct |
29 ms |
492 KB |
Output is correct |
12 |
Correct |
32 ms |
492 KB |
Output is correct |
13 |
Correct |
34 ms |
492 KB |
Output is correct |
14 |
Correct |
33 ms |
492 KB |
Output is correct |
15 |
Correct |
30 ms |
492 KB |
Output is correct |
16 |
Correct |
30 ms |
492 KB |
Output is correct |
17 |
Correct |
31 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1444 ms |
3112 KB |
Output is correct |
2 |
Correct |
1394 ms |
3112 KB |
Output is correct |
3 |
Correct |
1429 ms |
3236 KB |
Output is correct |
4 |
Correct |
1422 ms |
3192 KB |
Output is correct |
5 |
Correct |
1403 ms |
3240 KB |
Output is correct |
6 |
Correct |
2055 ms |
3380 KB |
Output is correct |
7 |
Correct |
2060 ms |
3268 KB |
Output is correct |
8 |
Correct |
2065 ms |
3116 KB |
Output is correct |
9 |
Correct |
59 ms |
2028 KB |
Output is correct |
10 |
Correct |
1387 ms |
3060 KB |
Output is correct |
11 |
Correct |
1297 ms |
2856 KB |
Output is correct |
12 |
Correct |
1271 ms |
3648 KB |
Output is correct |
13 |
Correct |
1117 ms |
2856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1123 ms |
2764 KB |
Output is correct |
2 |
Correct |
929 ms |
2124 KB |
Output is correct |
3 |
Correct |
1300 ms |
2664 KB |
Output is correct |
4 |
Correct |
1115 ms |
2664 KB |
Output is correct |
5 |
Correct |
61 ms |
2028 KB |
Output is correct |
6 |
Correct |
1255 ms |
2536 KB |
Output is correct |
7 |
Correct |
1066 ms |
2792 KB |
Output is correct |
8 |
Correct |
930 ms |
2956 KB |
Output is correct |
9 |
Correct |
736 ms |
2920 KB |
Output is correct |
10 |
Correct |
658 ms |
2920 KB |
Output is correct |
11 |
Correct |
717 ms |
2536 KB |
Output is correct |
12 |
Correct |
613 ms |
2408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1034 ms |
4552 KB |
Output is correct |
2 |
Correct |
60 ms |
2156 KB |
Output is correct |
3 |
Correct |
125 ms |
2156 KB |
Output is correct |
4 |
Correct |
104 ms |
2156 KB |
Output is correct |
5 |
Correct |
733 ms |
4336 KB |
Output is correct |
6 |
Correct |
1028 ms |
4304 KB |
Output is correct |
7 |
Correct |
788 ms |
4264 KB |
Output is correct |
8 |
Correct |
514 ms |
3112 KB |
Output is correct |
9 |
Correct |
503 ms |
3112 KB |
Output is correct |
10 |
Correct |
539 ms |
3360 KB |
Output is correct |
11 |
Correct |
849 ms |
3752 KB |
Output is correct |
12 |
Correct |
847 ms |
3624 KB |
Output is correct |
13 |
Correct |
840 ms |
3884 KB |
Output is correct |
14 |
Correct |
690 ms |
4292 KB |
Output is correct |
15 |
Correct |
674 ms |
4264 KB |
Output is correct |
16 |
Correct |
1128 ms |
4268 KB |
Output is correct |
17 |
Correct |
1145 ms |
4368 KB |
Output is correct |
18 |
Correct |
1085 ms |
4200 KB |
Output is correct |
19 |
Correct |
1095 ms |
4152 KB |
Output is correct |
20 |
Correct |
974 ms |
4124 KB |
Output is correct |
21 |
Correct |
991 ms |
4136 KB |
Output is correct |
22 |
Correct |
1090 ms |
4268 KB |
Output is correct |
23 |
Correct |
791 ms |
4028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1444 ms |
3112 KB |
Output is correct |
2 |
Correct |
1394 ms |
3112 KB |
Output is correct |
3 |
Correct |
1429 ms |
3236 KB |
Output is correct |
4 |
Correct |
1422 ms |
3192 KB |
Output is correct |
5 |
Correct |
1403 ms |
3240 KB |
Output is correct |
6 |
Correct |
2055 ms |
3380 KB |
Output is correct |
7 |
Correct |
2060 ms |
3268 KB |
Output is correct |
8 |
Correct |
2065 ms |
3116 KB |
Output is correct |
9 |
Correct |
59 ms |
2028 KB |
Output is correct |
10 |
Correct |
1387 ms |
3060 KB |
Output is correct |
11 |
Correct |
1297 ms |
2856 KB |
Output is correct |
12 |
Correct |
1271 ms |
3648 KB |
Output is correct |
13 |
Correct |
1117 ms |
2856 KB |
Output is correct |
14 |
Correct |
1123 ms |
2764 KB |
Output is correct |
15 |
Correct |
929 ms |
2124 KB |
Output is correct |
16 |
Correct |
1300 ms |
2664 KB |
Output is correct |
17 |
Correct |
1115 ms |
2664 KB |
Output is correct |
18 |
Correct |
61 ms |
2028 KB |
Output is correct |
19 |
Correct |
1255 ms |
2536 KB |
Output is correct |
20 |
Correct |
1066 ms |
2792 KB |
Output is correct |
21 |
Correct |
930 ms |
2956 KB |
Output is correct |
22 |
Correct |
736 ms |
2920 KB |
Output is correct |
23 |
Correct |
658 ms |
2920 KB |
Output is correct |
24 |
Correct |
717 ms |
2536 KB |
Output is correct |
25 |
Correct |
613 ms |
2408 KB |
Output is correct |
26 |
Correct |
1423 ms |
2840 KB |
Output is correct |
27 |
Correct |
1740 ms |
2856 KB |
Output is correct |
28 |
Correct |
1500 ms |
2872 KB |
Output is correct |
29 |
Correct |
1096 ms |
3104 KB |
Output is correct |
30 |
Correct |
1741 ms |
3132 KB |
Output is correct |
31 |
Correct |
1774 ms |
3068 KB |
Output is correct |
32 |
Correct |
1769 ms |
3220 KB |
Output is correct |
33 |
Correct |
1535 ms |
2868 KB |
Output is correct |
34 |
Correct |
1527 ms |
2980 KB |
Output is correct |
35 |
Correct |
1549 ms |
3108 KB |
Output is correct |
36 |
Correct |
1157 ms |
2856 KB |
Output is correct |
37 |
Correct |
1156 ms |
2828 KB |
Output is correct |
38 |
Correct |
1136 ms |
2852 KB |
Output is correct |
39 |
Correct |
910 ms |
3112 KB |
Output is correct |
40 |
Correct |
948 ms |
3112 KB |
Output is correct |
41 |
Correct |
897 ms |
3128 KB |
Output is correct |
42 |
Correct |
820 ms |
2728 KB |
Output is correct |
43 |
Correct |
814 ms |
2856 KB |
Output is correct |
44 |
Correct |
799 ms |
2856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
31 ms |
492 KB |
Output is correct |
4 |
Correct |
6 ms |
620 KB |
Output is correct |
5 |
Correct |
25 ms |
492 KB |
Output is correct |
6 |
Correct |
23 ms |
492 KB |
Output is correct |
7 |
Correct |
28 ms |
492 KB |
Output is correct |
8 |
Correct |
33 ms |
492 KB |
Output is correct |
9 |
Correct |
33 ms |
492 KB |
Output is correct |
10 |
Correct |
30 ms |
492 KB |
Output is correct |
11 |
Correct |
29 ms |
492 KB |
Output is correct |
12 |
Correct |
32 ms |
492 KB |
Output is correct |
13 |
Correct |
34 ms |
492 KB |
Output is correct |
14 |
Correct |
33 ms |
492 KB |
Output is correct |
15 |
Correct |
30 ms |
492 KB |
Output is correct |
16 |
Correct |
30 ms |
492 KB |
Output is correct |
17 |
Correct |
31 ms |
620 KB |
Output is correct |
18 |
Correct |
1444 ms |
3112 KB |
Output is correct |
19 |
Correct |
1394 ms |
3112 KB |
Output is correct |
20 |
Correct |
1429 ms |
3236 KB |
Output is correct |
21 |
Correct |
1422 ms |
3192 KB |
Output is correct |
22 |
Correct |
1403 ms |
3240 KB |
Output is correct |
23 |
Correct |
2055 ms |
3380 KB |
Output is correct |
24 |
Correct |
2060 ms |
3268 KB |
Output is correct |
25 |
Correct |
2065 ms |
3116 KB |
Output is correct |
26 |
Correct |
59 ms |
2028 KB |
Output is correct |
27 |
Correct |
1387 ms |
3060 KB |
Output is correct |
28 |
Correct |
1297 ms |
2856 KB |
Output is correct |
29 |
Correct |
1271 ms |
3648 KB |
Output is correct |
30 |
Correct |
1117 ms |
2856 KB |
Output is correct |
31 |
Correct |
1123 ms |
2764 KB |
Output is correct |
32 |
Correct |
929 ms |
2124 KB |
Output is correct |
33 |
Correct |
1300 ms |
2664 KB |
Output is correct |
34 |
Correct |
1115 ms |
2664 KB |
Output is correct |
35 |
Correct |
61 ms |
2028 KB |
Output is correct |
36 |
Correct |
1255 ms |
2536 KB |
Output is correct |
37 |
Correct |
1066 ms |
2792 KB |
Output is correct |
38 |
Correct |
930 ms |
2956 KB |
Output is correct |
39 |
Correct |
736 ms |
2920 KB |
Output is correct |
40 |
Correct |
658 ms |
2920 KB |
Output is correct |
41 |
Correct |
717 ms |
2536 KB |
Output is correct |
42 |
Correct |
613 ms |
2408 KB |
Output is correct |
43 |
Correct |
1034 ms |
4552 KB |
Output is correct |
44 |
Correct |
60 ms |
2156 KB |
Output is correct |
45 |
Correct |
125 ms |
2156 KB |
Output is correct |
46 |
Correct |
104 ms |
2156 KB |
Output is correct |
47 |
Correct |
733 ms |
4336 KB |
Output is correct |
48 |
Correct |
1028 ms |
4304 KB |
Output is correct |
49 |
Correct |
788 ms |
4264 KB |
Output is correct |
50 |
Correct |
514 ms |
3112 KB |
Output is correct |
51 |
Correct |
503 ms |
3112 KB |
Output is correct |
52 |
Correct |
539 ms |
3360 KB |
Output is correct |
53 |
Correct |
849 ms |
3752 KB |
Output is correct |
54 |
Correct |
847 ms |
3624 KB |
Output is correct |
55 |
Correct |
840 ms |
3884 KB |
Output is correct |
56 |
Correct |
690 ms |
4292 KB |
Output is correct |
57 |
Correct |
674 ms |
4264 KB |
Output is correct |
58 |
Correct |
1128 ms |
4268 KB |
Output is correct |
59 |
Correct |
1145 ms |
4368 KB |
Output is correct |
60 |
Correct |
1085 ms |
4200 KB |
Output is correct |
61 |
Correct |
1095 ms |
4152 KB |
Output is correct |
62 |
Correct |
974 ms |
4124 KB |
Output is correct |
63 |
Correct |
991 ms |
4136 KB |
Output is correct |
64 |
Correct |
1090 ms |
4268 KB |
Output is correct |
65 |
Correct |
791 ms |
4028 KB |
Output is correct |
66 |
Correct |
1423 ms |
2840 KB |
Output is correct |
67 |
Correct |
1740 ms |
2856 KB |
Output is correct |
68 |
Correct |
1500 ms |
2872 KB |
Output is correct |
69 |
Correct |
1096 ms |
3104 KB |
Output is correct |
70 |
Correct |
1741 ms |
3132 KB |
Output is correct |
71 |
Correct |
1774 ms |
3068 KB |
Output is correct |
72 |
Correct |
1769 ms |
3220 KB |
Output is correct |
73 |
Correct |
1535 ms |
2868 KB |
Output is correct |
74 |
Correct |
1527 ms |
2980 KB |
Output is correct |
75 |
Correct |
1549 ms |
3108 KB |
Output is correct |
76 |
Correct |
1157 ms |
2856 KB |
Output is correct |
77 |
Correct |
1156 ms |
2828 KB |
Output is correct |
78 |
Correct |
1136 ms |
2852 KB |
Output is correct |
79 |
Correct |
910 ms |
3112 KB |
Output is correct |
80 |
Correct |
948 ms |
3112 KB |
Output is correct |
81 |
Correct |
897 ms |
3128 KB |
Output is correct |
82 |
Correct |
820 ms |
2728 KB |
Output is correct |
83 |
Correct |
814 ms |
2856 KB |
Output is correct |
84 |
Correct |
799 ms |
2856 KB |
Output is correct |
85 |
Correct |
2104 ms |
4136 KB |
Output is correct |
86 |
Correct |
218 ms |
2028 KB |
Output is correct |
87 |
Correct |
129 ms |
2156 KB |
Output is correct |
88 |
Correct |
1256 ms |
4012 KB |
Output is correct |
89 |
Correct |
2088 ms |
3940 KB |
Output is correct |
90 |
Correct |
1218 ms |
4028 KB |
Output is correct |
91 |
Correct |
1523 ms |
2800 KB |
Output is correct |
92 |
Correct |
1536 ms |
3376 KB |
Output is correct |
93 |
Correct |
2218 ms |
3160 KB |
Output is correct |
94 |
Correct |
1833 ms |
3464 KB |
Output is correct |
95 |
Correct |
1772 ms |
3496 KB |
Output is correct |
96 |
Correct |
1786 ms |
3368 KB |
Output is correct |
97 |
Correct |
912 ms |
4264 KB |
Output is correct |
98 |
Correct |
1016 ms |
3368 KB |
Output is correct |
99 |
Correct |
2180 ms |
4008 KB |
Output is correct |
100 |
Correct |
2128 ms |
3864 KB |
Output is correct |
101 |
Correct |
2314 ms |
3752 KB |
Output is correct |
102 |
Correct |
2197 ms |
3736 KB |
Output is correct |
103 |
Correct |
1897 ms |
3788 KB |
Output is correct |
104 |
Correct |
1874 ms |
3752 KB |
Output is correct |
105 |
Correct |
1496 ms |
3124 KB |
Output is correct |
106 |
Correct |
1235 ms |
3112 KB |
Output is correct |
107 |
Correct |
1618 ms |
3884 KB |
Output is correct |
108 |
Correct |
2029 ms |
3792 KB |
Output is correct |
109 |
Correct |
1238 ms |
3516 KB |
Output is correct |