#include <bits/stdc++.h>
#define nl '\n'
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
struct DSU {
std::vector<int> e;
std::vector<std::array<int, 4>> trace;
DSU(int n) : e(n, -1) {}
int find(int u) {
return e[u] < 0 ? u : find(e[u]);
}
bool merge(int u, int v) {
trace.push_back({-1, -1, -1, -1});
u = find(u), v = find(v);
if (u == v) return false;
if (e[u] > e[v]) std::swap(u, v);
trace.back() = {u, e[u], v, e[v]};
e[u] += e[v];
e[v] = u;
return true;
}
void rollback() {
auto [u, eu, v, ev] = trace.back();
trace.pop_back();
if (u != -1) {
e[u] = eu;
e[v] = ev;
}
}
void rollback(int size) {
while ((int) trace.size() > size) {
rollback();
}
}
int history_size() const {
return trace.size();
}
bool same(int u, int v) {
return find(u) == find(v);
}
int size(int u) {
return -e[find(u)];
}
};
struct Edge {
int u, v, d, i;
bool operator<(const Edge& rhs) const {
return d < rhs.d;
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::array<int, 3>> edges(m);
for (int i = 0; i < m; i++) {
int u, v, d;
std::cin >> u >> v >> d;
--u, --v;
edges[i] = {d, u, v};
}
int q;
std::cin >> q;
std::vector<int> ans(q, -1);
const int B = 200;
std::vector<int> is_changed(m, -1);
std::vector<int> become(m, -1);
std::vector<std::array<int, 3>> unchanged;
std::vector<int> changed;
unchanged.reserve(m);
changed.reserve(m);
for (int lb = 0; lb < q; lb += B) {
int rb = std::min(lb + B, q);
std::vector<std::array<int, 3>> ask;
std::vector<std::array<int, 3>> upd;
for (int i = lb; i < rb; i++) {
int t, a, b;
std::cin >> t >> a >> b;
--a;
if (t == 1) {
is_changed[a] = lb;
upd.push_back({b, a, i});
} else {
ask.push_back({b, a, i});
}
}
unchanged.clear();
changed.clear();
for (int i = 0; i < m; i++) {
if (is_changed[i] < lb) {
unchanged.emplace_back(edges[i]);
} else {
changed.emplace_back(i);
}
}
std::sort(unchanged.rbegin(), unchanged.rend());
DSU dsu(n);
int j = 0;
std::sort(ask.rbegin(), ask.rend());
for (auto [w, s, id] : ask) {
while (j < (int) unchanged.size() && unchanged[j][0] >= w) {
dsu.merge(unchanged[j][1], unchanged[j][2]);
j++;
}
int sz = dsu.history_size();
for (auto [r, b, uid] : upd) {
if (uid <= id) {
become[b] = r;
}
}
for (int i : changed) {
auto [d, u, v] = edges[i];
if (become[i] != -1) d = become[i];
if (d >= w) {
dsu.merge(u, v);
}
}
for (auto [r, b, uid] : upd) {
if (uid <= id) {
become[b] = -1;
}
}
ans[id] = dsu.size(s);
dsu.rollback(sz);
}
for (auto [r, b, uid] : upd) {
edges[b][0] = r;
}
}
for (int i = 0; i < q; i++) {
if (ans[i] != -1) std::cout << ans[i] << nl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
11 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
608 KB |
Output is correct |
5 |
Correct |
6 ms |
604 KB |
Output is correct |
6 |
Correct |
6 ms |
604 KB |
Output is correct |
7 |
Correct |
6 ms |
604 KB |
Output is correct |
8 |
Correct |
8 ms |
464 KB |
Output is correct |
9 |
Correct |
7 ms |
604 KB |
Output is correct |
10 |
Correct |
6 ms |
616 KB |
Output is correct |
11 |
Correct |
8 ms |
600 KB |
Output is correct |
12 |
Correct |
7 ms |
652 KB |
Output is correct |
13 |
Correct |
8 ms |
604 KB |
Output is correct |
14 |
Correct |
8 ms |
624 KB |
Output is correct |
15 |
Correct |
7 ms |
604 KB |
Output is correct |
16 |
Correct |
6 ms |
348 KB |
Output is correct |
17 |
Correct |
6 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2746 ms |
5556 KB |
Output is correct |
2 |
Correct |
2896 ms |
7156 KB |
Output is correct |
3 |
Correct |
2839 ms |
7160 KB |
Output is correct |
4 |
Correct |
2734 ms |
7272 KB |
Output is correct |
5 |
Correct |
2793 ms |
7644 KB |
Output is correct |
6 |
Correct |
2929 ms |
7032 KB |
Output is correct |
7 |
Correct |
2891 ms |
6992 KB |
Output is correct |
8 |
Correct |
2914 ms |
7160 KB |
Output is correct |
9 |
Correct |
25 ms |
2392 KB |
Output is correct |
10 |
Correct |
2715 ms |
6244 KB |
Output is correct |
11 |
Correct |
2874 ms |
6068 KB |
Output is correct |
12 |
Correct |
2869 ms |
6896 KB |
Output is correct |
13 |
Correct |
2819 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1776 ms |
4384 KB |
Output is correct |
2 |
Correct |
454 ms |
3320 KB |
Output is correct |
3 |
Correct |
1761 ms |
5276 KB |
Output is correct |
4 |
Correct |
1745 ms |
5632 KB |
Output is correct |
5 |
Correct |
26 ms |
2384 KB |
Output is correct |
6 |
Correct |
1731 ms |
5300 KB |
Output is correct |
7 |
Correct |
1731 ms |
5324 KB |
Output is correct |
8 |
Correct |
1742 ms |
5472 KB |
Output is correct |
9 |
Correct |
1775 ms |
5424 KB |
Output is correct |
10 |
Correct |
1710 ms |
5328 KB |
Output is correct |
11 |
Correct |
1713 ms |
5300 KB |
Output is correct |
12 |
Correct |
1727 ms |
5388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3011 ms |
8184 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2746 ms |
5556 KB |
Output is correct |
2 |
Correct |
2896 ms |
7156 KB |
Output is correct |
3 |
Correct |
2839 ms |
7160 KB |
Output is correct |
4 |
Correct |
2734 ms |
7272 KB |
Output is correct |
5 |
Correct |
2793 ms |
7644 KB |
Output is correct |
6 |
Correct |
2929 ms |
7032 KB |
Output is correct |
7 |
Correct |
2891 ms |
6992 KB |
Output is correct |
8 |
Correct |
2914 ms |
7160 KB |
Output is correct |
9 |
Correct |
25 ms |
2392 KB |
Output is correct |
10 |
Correct |
2715 ms |
6244 KB |
Output is correct |
11 |
Correct |
2874 ms |
6068 KB |
Output is correct |
12 |
Correct |
2869 ms |
6896 KB |
Output is correct |
13 |
Correct |
2819 ms |
7516 KB |
Output is correct |
14 |
Correct |
1776 ms |
4384 KB |
Output is correct |
15 |
Correct |
454 ms |
3320 KB |
Output is correct |
16 |
Correct |
1761 ms |
5276 KB |
Output is correct |
17 |
Correct |
1745 ms |
5632 KB |
Output is correct |
18 |
Correct |
26 ms |
2384 KB |
Output is correct |
19 |
Correct |
1731 ms |
5300 KB |
Output is correct |
20 |
Correct |
1731 ms |
5324 KB |
Output is correct |
21 |
Correct |
1742 ms |
5472 KB |
Output is correct |
22 |
Correct |
1775 ms |
5424 KB |
Output is correct |
23 |
Correct |
1710 ms |
5328 KB |
Output is correct |
24 |
Correct |
1713 ms |
5300 KB |
Output is correct |
25 |
Correct |
1727 ms |
5388 KB |
Output is correct |
26 |
Correct |
2830 ms |
7352 KB |
Output is correct |
27 |
Correct |
2938 ms |
7152 KB |
Output is correct |
28 |
Correct |
2921 ms |
7304 KB |
Output is correct |
29 |
Correct |
2868 ms |
7208 KB |
Output is correct |
30 |
Correct |
2917 ms |
7264 KB |
Output is correct |
31 |
Correct |
2862 ms |
7020 KB |
Output is correct |
32 |
Correct |
2924 ms |
7032 KB |
Output is correct |
33 |
Correct |
2891 ms |
7236 KB |
Output is correct |
34 |
Correct |
2936 ms |
7224 KB |
Output is correct |
35 |
Execution timed out |
3064 ms |
7228 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
11 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
608 KB |
Output is correct |
5 |
Correct |
6 ms |
604 KB |
Output is correct |
6 |
Correct |
6 ms |
604 KB |
Output is correct |
7 |
Correct |
6 ms |
604 KB |
Output is correct |
8 |
Correct |
8 ms |
464 KB |
Output is correct |
9 |
Correct |
7 ms |
604 KB |
Output is correct |
10 |
Correct |
6 ms |
616 KB |
Output is correct |
11 |
Correct |
8 ms |
600 KB |
Output is correct |
12 |
Correct |
7 ms |
652 KB |
Output is correct |
13 |
Correct |
8 ms |
604 KB |
Output is correct |
14 |
Correct |
8 ms |
624 KB |
Output is correct |
15 |
Correct |
7 ms |
604 KB |
Output is correct |
16 |
Correct |
6 ms |
348 KB |
Output is correct |
17 |
Correct |
6 ms |
468 KB |
Output is correct |
18 |
Correct |
2746 ms |
5556 KB |
Output is correct |
19 |
Correct |
2896 ms |
7156 KB |
Output is correct |
20 |
Correct |
2839 ms |
7160 KB |
Output is correct |
21 |
Correct |
2734 ms |
7272 KB |
Output is correct |
22 |
Correct |
2793 ms |
7644 KB |
Output is correct |
23 |
Correct |
2929 ms |
7032 KB |
Output is correct |
24 |
Correct |
2891 ms |
6992 KB |
Output is correct |
25 |
Correct |
2914 ms |
7160 KB |
Output is correct |
26 |
Correct |
25 ms |
2392 KB |
Output is correct |
27 |
Correct |
2715 ms |
6244 KB |
Output is correct |
28 |
Correct |
2874 ms |
6068 KB |
Output is correct |
29 |
Correct |
2869 ms |
6896 KB |
Output is correct |
30 |
Correct |
2819 ms |
7516 KB |
Output is correct |
31 |
Correct |
1776 ms |
4384 KB |
Output is correct |
32 |
Correct |
454 ms |
3320 KB |
Output is correct |
33 |
Correct |
1761 ms |
5276 KB |
Output is correct |
34 |
Correct |
1745 ms |
5632 KB |
Output is correct |
35 |
Correct |
26 ms |
2384 KB |
Output is correct |
36 |
Correct |
1731 ms |
5300 KB |
Output is correct |
37 |
Correct |
1731 ms |
5324 KB |
Output is correct |
38 |
Correct |
1742 ms |
5472 KB |
Output is correct |
39 |
Correct |
1775 ms |
5424 KB |
Output is correct |
40 |
Correct |
1710 ms |
5328 KB |
Output is correct |
41 |
Correct |
1713 ms |
5300 KB |
Output is correct |
42 |
Correct |
1727 ms |
5388 KB |
Output is correct |
43 |
Execution timed out |
3011 ms |
8184 KB |
Time limit exceeded |
44 |
Halted |
0 ms |
0 KB |
- |