이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define nl '\n'
struct DSU {
std::vector<int> e;
DSU(int n) : e(n, -1) {}
int find(int u) {
return e[u] < 0 ? u : e[u] = find(e[u]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
if (e[u] > e[v]) std::swap(u, v);
e[u] += e[v];
e[v] = u;
return true;
}
bool same(int u, int v) {
return find(u) == find(v);
}
int size(int u) {
return -e[find(u)];
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> adj(n);
struct Edge {
int u, v, d, i;
inline int other(int x) { return u ^ v ^ x; }
bool operator<(const Edge& rhs) {
return d < rhs.d;
}
};
// build a centroid or sth
std::vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
int u, v, d;
std::cin >> u >> v >> d;
--u, --v;
adj[u].emplace_back(i);
adj[v].emplace_back(i);
edges[i] = {u, v, d, i};
}
auto e = edges;
std::sort(e.rbegin(), e.rend());
DSU dsu(n);
int q;
std::cin >> q;
std::vector<std::array<int, 3>> queries;
std::vector<int> ans(q, -1);
for (int i = 0; i < q; i++) {
int t, a, b;
std::cin >> t >> a >> b;
--a;
if (t == 2) {
queries.push_back({b, a, i});
}
}
std::sort(queries.rbegin(), queries.rend());
int j = 0;
for (int i = 0; i < (int) queries.size(); i++) {
while (j < m && e[j].d >= queries[i].at(0)) {
auto [u, v, d, id] = e[j];
dsu.merge(u, v);
j++;
}
ans[queries[i].at(2)] = dsu.size(queries[i].at(1));
}
for (int i = 0; i < q; i++) {
if (ans[i] != -1) std::cout << ans[i] << nl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |