#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
#ifdef HOME
#define LOCAL_CHECK(x) assert(x);
#else
#define LOCAL_CHECK(x)
#endif
// https://judge.yosupo.jp/submission/159946
template<bool _CompressPath = true>
class DSU {
public:
DSU(int n) : n(n) {
LOCAL_CHECK(n > 0);
link.resize(n, -1);
size.resize(n, 1);
}
int getRoot(int x) noexcept {
LOCAL_CHECK(0 <= x && x < n);
if (_CompressPath) {
return link[x] == -1 ? x : link[x] = getRoot(link[x]);
} else {
return link[x] == -1 ? x : getRoot(link[x]);
}
}
bool join(int x, int y) noexcept(_CompressPath) {
LOCAL_CHECK(0 <= x && x < n);
LOCAL_CHECK(0 <= y && y < n);
x = getRoot(x), y = getRoot(y);
if (size[x] > size[y]) {
std::swap(x, y);
}
bool joined = (x != y);
if (joined) {
link[x] = y;
size[y] += size[x];
if (!_CompressPath) {
joinedLinks.push(x);
}
} else {
if (!_CompressPath) {
joinedLinks.push(-1);
}
}
return joined;
}
inline int getSize(int x) noexcept {
return size[getRoot(x)];
}
void undo() {
static_assert(!_CompressPath);
if (!joinedLinks.empty()) {
auto lastJoin = joinedLinks.top();
joinedLinks.pop();
if (lastJoin == -1) return;
size[link[lastJoin]] -= size[lastJoin];
link[lastJoin] = -1;
} else {
assert(false);
}
}
private:
std::vector<int> link;
std::vector<int> size;
int n;
std::stack<int> joinedLinks;
};
struct Edge {
int x, y, w;
};
struct Update {
int edgeId;
int w;
int pos;
};
struct Query {
int node;
int w;
int pos;
};
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<Edge> edges(m);
for (auto& e : edges) {
cin >> e.x >> e.y >> e.w;
}
vector<int> markedEdges(m, -1);
vector<int> markedUpdatedEdges(m, -1);
vector<int> edgeOrder(m);
iota(edgeOrder.begin(), edgeOrder.end(), 0);
DSU<false> dsu(n + 1);
const int LIM = 3 * sqrt(n);
int q;
cin >> q;
vector<int> result(q, -1);
for (int qq = 0; qq < q; qq += LIM) {
vector<Query> queries;
vector<Update> updates;
vector<int> currentEdges;
for (int i = 0; i < q - qq && i < LIM; i++) {
int t;
cin >> t;
if (t == 1) {
int edgeId, w;
cin >> edgeId >> w;
edgeId--;
updates.push_back({edgeId, w, i + qq});
if (markedEdges[edgeId] != qq) {
currentEdges.push_back(edgeId);
}
markedEdges[edgeId] = qq;
} else {
int node, w;
cin >> node >> w;
queries.push_back({node, w, i + qq});
}
}
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
return a.w > b.w;
});
sort(edgeOrder.begin(), edgeOrder.end(), [&](const int& a, const int& b) {
return edges[a].w > edges[b].w;
});
int pos = 0;
for (auto& query : queries) {
while (pos < m && edges[edgeOrder[pos]].w >= query.w) {
int edgeId = edgeOrder[pos];
if (markedEdges[edgeId] != qq) {
dsu.join(edges[edgeId].x, edges[edgeId].y);
}
pos++;
}
static int currentIteration = -1;
currentIteration++;
int i = 0;
while (i < (int)updates.size() && updates[i].pos <= query.pos) {
i++;
}
i--;
int j = 0;
while (i >= 0) {
int edgeId = updates[i].edgeId;
if (markedUpdatedEdges[edgeId] != currentIteration) {
markedUpdatedEdges[edgeId] = currentIteration;
if (query.w <= updates[i].w) {
dsu.join(edges[edgeId].x, edges[edgeId].y);
j++;
}
}
i--;
}
for (auto edgeId : currentEdges) {
if (markedUpdatedEdges[edgeId] != currentIteration && edges[edgeId].w >= query.w) {
dsu.join(edges[edgeId].x, edges[edgeId].y);
j++;
}
}
result[query.pos] = dsu.getSize(query.node);
while (j > 0) {
dsu.undo();
j--;
}
}
for (int i = pos - 1; i >= 0; i--) {
if (markedEdges[edgeOrder[i]] != qq) {
dsu.undo();
}
}
for (auto& update : updates) {
edges[update.edgeId].w = update.w;
}
}
for (auto itr : result) {
if (itr != -1) {
cout << itr << "\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
19 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
500 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
348 KB |
Output is correct |
12 |
Correct |
5 ms |
348 KB |
Output is correct |
13 |
Correct |
6 ms |
348 KB |
Output is correct |
14 |
Correct |
6 ms |
344 KB |
Output is correct |
15 |
Correct |
6 ms |
344 KB |
Output is correct |
16 |
Correct |
5 ms |
500 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
837 ms |
2648 KB |
Output is correct |
2 |
Correct |
820 ms |
2652 KB |
Output is correct |
3 |
Correct |
826 ms |
2648 KB |
Output is correct |
4 |
Correct |
855 ms |
2652 KB |
Output is correct |
5 |
Correct |
888 ms |
2908 KB |
Output is correct |
6 |
Correct |
1033 ms |
2896 KB |
Output is correct |
7 |
Correct |
1030 ms |
2888 KB |
Output is correct |
8 |
Correct |
1100 ms |
2896 KB |
Output is correct |
9 |
Correct |
27 ms |
856 KB |
Output is correct |
10 |
Correct |
598 ms |
2648 KB |
Output is correct |
11 |
Correct |
592 ms |
2652 KB |
Output is correct |
12 |
Correct |
789 ms |
2900 KB |
Output is correct |
13 |
Correct |
743 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
647 ms |
2304 KB |
Output is correct |
2 |
Correct |
282 ms |
1140 KB |
Output is correct |
3 |
Correct |
681 ms |
2132 KB |
Output is correct |
4 |
Correct |
636 ms |
2132 KB |
Output is correct |
5 |
Correct |
24 ms |
856 KB |
Output is correct |
6 |
Correct |
640 ms |
2040 KB |
Output is correct |
7 |
Correct |
589 ms |
2140 KB |
Output is correct |
8 |
Correct |
576 ms |
2384 KB |
Output is correct |
9 |
Correct |
597 ms |
2288 KB |
Output is correct |
10 |
Correct |
539 ms |
2168 KB |
Output is correct |
11 |
Correct |
506 ms |
2036 KB |
Output is correct |
12 |
Correct |
511 ms |
2136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1018 ms |
4220 KB |
Output is correct |
2 |
Correct |
24 ms |
852 KB |
Output is correct |
3 |
Correct |
858 ms |
3704 KB |
Output is correct |
4 |
Correct |
636 ms |
3432 KB |
Output is correct |
5 |
Correct |
865 ms |
4468 KB |
Output is correct |
6 |
Correct |
973 ms |
4372 KB |
Output is correct |
7 |
Correct |
896 ms |
4540 KB |
Output is correct |
8 |
Correct |
425 ms |
2648 KB |
Output is correct |
9 |
Correct |
417 ms |
2652 KB |
Output is correct |
10 |
Correct |
444 ms |
3104 KB |
Output is correct |
11 |
Correct |
758 ms |
3412 KB |
Output is correct |
12 |
Correct |
692 ms |
3336 KB |
Output is correct |
13 |
Correct |
748 ms |
3668 KB |
Output is correct |
14 |
Correct |
822 ms |
4380 KB |
Output is correct |
15 |
Correct |
829 ms |
4580 KB |
Output is correct |
16 |
Correct |
1031 ms |
4472 KB |
Output is correct |
17 |
Correct |
1047 ms |
4528 KB |
Output is correct |
18 |
Correct |
1012 ms |
7996 KB |
Output is correct |
19 |
Correct |
996 ms |
8352 KB |
Output is correct |
20 |
Correct |
917 ms |
7236 KB |
Output is correct |
21 |
Correct |
877 ms |
7196 KB |
Output is correct |
22 |
Correct |
1041 ms |
8124 KB |
Output is correct |
23 |
Correct |
835 ms |
6016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
837 ms |
2648 KB |
Output is correct |
2 |
Correct |
820 ms |
2652 KB |
Output is correct |
3 |
Correct |
826 ms |
2648 KB |
Output is correct |
4 |
Correct |
855 ms |
2652 KB |
Output is correct |
5 |
Correct |
888 ms |
2908 KB |
Output is correct |
6 |
Correct |
1033 ms |
2896 KB |
Output is correct |
7 |
Correct |
1030 ms |
2888 KB |
Output is correct |
8 |
Correct |
1100 ms |
2896 KB |
Output is correct |
9 |
Correct |
27 ms |
856 KB |
Output is correct |
10 |
Correct |
598 ms |
2648 KB |
Output is correct |
11 |
Correct |
592 ms |
2652 KB |
Output is correct |
12 |
Correct |
789 ms |
2900 KB |
Output is correct |
13 |
Correct |
743 ms |
2652 KB |
Output is correct |
14 |
Correct |
647 ms |
2304 KB |
Output is correct |
15 |
Correct |
282 ms |
1140 KB |
Output is correct |
16 |
Correct |
681 ms |
2132 KB |
Output is correct |
17 |
Correct |
636 ms |
2132 KB |
Output is correct |
18 |
Correct |
24 ms |
856 KB |
Output is correct |
19 |
Correct |
640 ms |
2040 KB |
Output is correct |
20 |
Correct |
589 ms |
2140 KB |
Output is correct |
21 |
Correct |
576 ms |
2384 KB |
Output is correct |
22 |
Correct |
597 ms |
2288 KB |
Output is correct |
23 |
Correct |
539 ms |
2168 KB |
Output is correct |
24 |
Correct |
506 ms |
2036 KB |
Output is correct |
25 |
Correct |
511 ms |
2136 KB |
Output is correct |
26 |
Correct |
901 ms |
2648 KB |
Output is correct |
27 |
Correct |
941 ms |
2648 KB |
Output is correct |
28 |
Correct |
844 ms |
2648 KB |
Output is correct |
29 |
Correct |
784 ms |
2648 KB |
Output is correct |
30 |
Correct |
950 ms |
2652 KB |
Output is correct |
31 |
Correct |
890 ms |
2636 KB |
Output is correct |
32 |
Correct |
933 ms |
2904 KB |
Output is correct |
33 |
Correct |
863 ms |
2652 KB |
Output is correct |
34 |
Correct |
859 ms |
2648 KB |
Output is correct |
35 |
Correct |
837 ms |
2652 KB |
Output is correct |
36 |
Correct |
762 ms |
2652 KB |
Output is correct |
37 |
Correct |
728 ms |
2636 KB |
Output is correct |
38 |
Correct |
757 ms |
2648 KB |
Output is correct |
39 |
Correct |
696 ms |
2652 KB |
Output is correct |
40 |
Correct |
742 ms |
2644 KB |
Output is correct |
41 |
Correct |
686 ms |
2648 KB |
Output is correct |
42 |
Correct |
636 ms |
2652 KB |
Output is correct |
43 |
Correct |
641 ms |
2636 KB |
Output is correct |
44 |
Correct |
619 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
19 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
348 KB |
Output is correct |
6 |
Correct |
5 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
500 KB |
Output is correct |
9 |
Correct |
5 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
348 KB |
Output is correct |
11 |
Correct |
5 ms |
348 KB |
Output is correct |
12 |
Correct |
5 ms |
348 KB |
Output is correct |
13 |
Correct |
6 ms |
348 KB |
Output is correct |
14 |
Correct |
6 ms |
344 KB |
Output is correct |
15 |
Correct |
6 ms |
344 KB |
Output is correct |
16 |
Correct |
5 ms |
500 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
18 |
Correct |
837 ms |
2648 KB |
Output is correct |
19 |
Correct |
820 ms |
2652 KB |
Output is correct |
20 |
Correct |
826 ms |
2648 KB |
Output is correct |
21 |
Correct |
855 ms |
2652 KB |
Output is correct |
22 |
Correct |
888 ms |
2908 KB |
Output is correct |
23 |
Correct |
1033 ms |
2896 KB |
Output is correct |
24 |
Correct |
1030 ms |
2888 KB |
Output is correct |
25 |
Correct |
1100 ms |
2896 KB |
Output is correct |
26 |
Correct |
27 ms |
856 KB |
Output is correct |
27 |
Correct |
598 ms |
2648 KB |
Output is correct |
28 |
Correct |
592 ms |
2652 KB |
Output is correct |
29 |
Correct |
789 ms |
2900 KB |
Output is correct |
30 |
Correct |
743 ms |
2652 KB |
Output is correct |
31 |
Correct |
647 ms |
2304 KB |
Output is correct |
32 |
Correct |
282 ms |
1140 KB |
Output is correct |
33 |
Correct |
681 ms |
2132 KB |
Output is correct |
34 |
Correct |
636 ms |
2132 KB |
Output is correct |
35 |
Correct |
24 ms |
856 KB |
Output is correct |
36 |
Correct |
640 ms |
2040 KB |
Output is correct |
37 |
Correct |
589 ms |
2140 KB |
Output is correct |
38 |
Correct |
576 ms |
2384 KB |
Output is correct |
39 |
Correct |
597 ms |
2288 KB |
Output is correct |
40 |
Correct |
539 ms |
2168 KB |
Output is correct |
41 |
Correct |
506 ms |
2036 KB |
Output is correct |
42 |
Correct |
511 ms |
2136 KB |
Output is correct |
43 |
Correct |
1018 ms |
4220 KB |
Output is correct |
44 |
Correct |
24 ms |
852 KB |
Output is correct |
45 |
Correct |
858 ms |
3704 KB |
Output is correct |
46 |
Correct |
636 ms |
3432 KB |
Output is correct |
47 |
Correct |
865 ms |
4468 KB |
Output is correct |
48 |
Correct |
973 ms |
4372 KB |
Output is correct |
49 |
Correct |
896 ms |
4540 KB |
Output is correct |
50 |
Correct |
425 ms |
2648 KB |
Output is correct |
51 |
Correct |
417 ms |
2652 KB |
Output is correct |
52 |
Correct |
444 ms |
3104 KB |
Output is correct |
53 |
Correct |
758 ms |
3412 KB |
Output is correct |
54 |
Correct |
692 ms |
3336 KB |
Output is correct |
55 |
Correct |
748 ms |
3668 KB |
Output is correct |
56 |
Correct |
822 ms |
4380 KB |
Output is correct |
57 |
Correct |
829 ms |
4580 KB |
Output is correct |
58 |
Correct |
1031 ms |
4472 KB |
Output is correct |
59 |
Correct |
1047 ms |
4528 KB |
Output is correct |
60 |
Correct |
1012 ms |
7996 KB |
Output is correct |
61 |
Correct |
996 ms |
8352 KB |
Output is correct |
62 |
Correct |
917 ms |
7236 KB |
Output is correct |
63 |
Correct |
877 ms |
7196 KB |
Output is correct |
64 |
Correct |
1041 ms |
8124 KB |
Output is correct |
65 |
Correct |
835 ms |
6016 KB |
Output is correct |
66 |
Correct |
901 ms |
2648 KB |
Output is correct |
67 |
Correct |
941 ms |
2648 KB |
Output is correct |
68 |
Correct |
844 ms |
2648 KB |
Output is correct |
69 |
Correct |
784 ms |
2648 KB |
Output is correct |
70 |
Correct |
950 ms |
2652 KB |
Output is correct |
71 |
Correct |
890 ms |
2636 KB |
Output is correct |
72 |
Correct |
933 ms |
2904 KB |
Output is correct |
73 |
Correct |
863 ms |
2652 KB |
Output is correct |
74 |
Correct |
859 ms |
2648 KB |
Output is correct |
75 |
Correct |
837 ms |
2652 KB |
Output is correct |
76 |
Correct |
762 ms |
2652 KB |
Output is correct |
77 |
Correct |
728 ms |
2636 KB |
Output is correct |
78 |
Correct |
757 ms |
2648 KB |
Output is correct |
79 |
Correct |
696 ms |
2652 KB |
Output is correct |
80 |
Correct |
742 ms |
2644 KB |
Output is correct |
81 |
Correct |
686 ms |
2648 KB |
Output is correct |
82 |
Correct |
636 ms |
2652 KB |
Output is correct |
83 |
Correct |
641 ms |
2636 KB |
Output is correct |
84 |
Correct |
619 ms |
2652 KB |
Output is correct |
85 |
Correct |
1737 ms |
8252 KB |
Output is correct |
86 |
Correct |
1322 ms |
5316 KB |
Output is correct |
87 |
Correct |
625 ms |
5488 KB |
Output is correct |
88 |
Correct |
1045 ms |
6544 KB |
Output is correct |
89 |
Correct |
1709 ms |
8016 KB |
Output is correct |
90 |
Correct |
1114 ms |
6468 KB |
Output is correct |
91 |
Correct |
904 ms |
5460 KB |
Output is correct |
92 |
Correct |
849 ms |
5456 KB |
Output is correct |
93 |
Correct |
1035 ms |
5456 KB |
Output is correct |
94 |
Correct |
1307 ms |
6504 KB |
Output is correct |
95 |
Correct |
1286 ms |
6688 KB |
Output is correct |
96 |
Correct |
1388 ms |
6476 KB |
Output is correct |
97 |
Correct |
914 ms |
6500 KB |
Output is correct |
98 |
Correct |
995 ms |
6484 KB |
Output is correct |
99 |
Correct |
1684 ms |
7948 KB |
Output is correct |
100 |
Correct |
1779 ms |
7788 KB |
Output is correct |
101 |
Correct |
1755 ms |
8024 KB |
Output is correct |
102 |
Correct |
1693 ms |
7856 KB |
Output is correct |
103 |
Correct |
1552 ms |
7096 KB |
Output is correct |
104 |
Correct |
1554 ms |
7172 KB |
Output is correct |
105 |
Correct |
1340 ms |
7376 KB |
Output is correct |
106 |
Correct |
1075 ms |
6400 KB |
Output is correct |
107 |
Correct |
1344 ms |
7160 KB |
Output is correct |
108 |
Correct |
1723 ms |
7960 KB |
Output is correct |
109 |
Correct |
1065 ms |
5712 KB |
Output is correct |