Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj/aoj_1645.test.cpp
- View this file on GitHub
- Last update: 2025-03-18 01:14:29+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1645
Depends on
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1645"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define all(v) (v).begin(), (v).end()
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
for (std::size_t i = 0; i < vec.size(); i++)
os << vec[i] << (i + 1 == vec.size() ? "" : " ");
return os;
}
#include "../../data_structure/segtree.hpp"
#include "../../data_structure/undo_unionfind.hpp"
namespace ebi {
using ld = long double;
constexpr int sz = 100010;
int op(int a, int b) {
return a > b ? a : b;
}
int e() {
return -1;
}
void main_() {
int n, m;
while (std::cin >> n >> m, !(n == 0 && m == 0)) {
std::vector<std::pair<int, int>> ab(m);
std::vector<int> s(m);
rep(i, 0, m) {
auto& [a, b] = ab[i];
std::cin >> a >> b >> s[i];
a--;
b--;
}
std::vector<int> idx(m);
std::iota(all(idx), 0);
std::sort(all(idx), [&](int i, int j) -> bool { return s[i] > s[j]; });
undo_unionfind uf(n);
std::vector table(sz, std::vector<int>());
for (auto i : idx) {
auto [a, b] = ab[i];
uf.merge(a, b);
table[s[i]].emplace_back(i);
}
segtree<int, op, e> seg(n);
rep(i, 0, n) {
if (uf.par[i] < 0) {
seg.set(i, -uf.par[i]);
}
}
std::vector<int> ret(n, 1);
rep(i, 0, sz) {
std::vector<int> vs;
std::reverse(all(table[i]));
for (auto id : table[i]) {
auto [a, b] = ab[id];
if (ret[uf.leader(a)] < 0) {
uf.undo();
a = uf.leader(a);
b = uf.leader(b);
ret[a] = -1;
ret[b] = -1;
continue;
}
seg.set(uf.leader(a), -1);
uf.undo();
a = uf.leader(a);
b = uf.leader(b);
seg.set(a, uf.size(a));
seg.set(b, uf.size(b));
vs.emplace_back(a);
vs.emplace_back(b);
}
int max = seg.all_prod();
for (auto v : vs) {
v = uf.leader(v);
if (uf.size(v) < max) {
seg.set(v, -1);
ret[v] = -1;
}
}
}
std::vector<int> ans;
rep(i, 0, n) if (ret[i] > 0) {
ans.emplace_back(i + 1);
}
std::cout << ans << '\n';
}
}
} // namespace ebi
int main() {
ebi::main_();
}#line 1 "test/aoj/aoj_1645.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1645"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define all(v) (v).begin(), (v).end()
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
for (std::size_t i = 0; i < vec.size(); i++)
os << vec[i] << (i + 1 == vec.size() ? "" : " ");
return os;
}
#line 2 "data_structure/segtree.hpp"
#include <cassert>
#line 5 "data_structure/segtree.hpp"
namespace ebi {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
private:
int n;
int sz;
std::vector<S> data;
void update(int i) {
data[i] = op(data[2 * i], data[2 * i + 1]);
}
public:
segtree(int n_) : segtree(std::vector<S>(n_, e())) {}
segtree(const std::vector<S> &v) : n((int)v.size()), sz(1) {
while (sz < n) sz *= 2;
data = std::vector<S>(2 * sz, e());
for (int i = 0; i < n; i++) {
data[sz + i] = v[i];
}
for (int i = sz - 1; i >= 1; i--) update(i);
}
void set(int p, S x) {
assert(0 <= p && p < n);
p += sz;
data[p] = x;
while (p > 1) {
p >>= 1;
update(p);
}
}
S get(int p) const {
assert(0 <= p && p < n);
return data[p + sz];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
S sml = e(), smr = e();
l += sz;
r += sz;
while (l < r) {
if (l & 1) sml = op(sml, data[l++]);
if (r & 1) smr = op(data[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const {
return data[1];
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l < n);
assert(f(e()));
if (l == n) return n;
l += sz;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, data[l]))) {
while (l < sz) {
l = 2 * l;
if (f(op(sm, data[l]))) {
sm = op(sm, data[l]);
l++;
}
}
return l - sz;
}
sm = op(sm, data[l]);
l++;
} while ((l & -l) != l);
return n;
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= n);
assert(f(e()));
if (r == 0) return 0;
r += sz;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(data[r], sm))) {
while (r < sz) {
r = 2 * r + 1;
if (f(op(data[r], sm))) {
sm = op(data[r], sm);
r--;
}
}
return r + 1 - sz;
}
sm = op(data[r], sm);
} while ((r & -r) != r);
return 0;
}
S operator[](int p) const {
return data[sz + p];
}
};
} // namespace ebi
#line 2 "data_structure/undo_unionfind.hpp"
#line 4 "data_structure/undo_unionfind.hpp"
#include <stack>
#line 6 "data_structure/undo_unionfind.hpp"
namespace ebi {
struct undo_unionfind {
private:
std::stack<std::pair<int, int> > stack;
public:
std::vector<int> par;
undo_unionfind(int n = 0) : par(n, -1) {}
bool same(int x, int y) const {
return leader(x) == leader(y);
}
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
stack.push({x, par[x]});
stack.push({y, par[y]});
if (x == y) return false;
if (par[x] > par[y]) std::swap(x, y);
par[x] += par[y];
par[y] = x;
return true;
}
int leader(int x) const {
if (par[x] < 0)
return x;
else
return leader(par[x]);
}
int size(int x) const {
return -par[leader(x)];
}
int count_group() const {
int c = 0;
for (int i = 0; i < int(par.size()); i++) {
if (par[i] < 0) c++;
}
return c;
}
void undo() {
assert(!stack.empty());
par[stack.top().first] = stack.top().second;
stack.pop();
par[stack.top().first] = stack.top().second;
stack.pop();
return;
}
};
} // namespace ebi
#line 20 "test/aoj/aoj_1645.test.cpp"
namespace ebi {
using ld = long double;
constexpr int sz = 100010;
int op(int a, int b) {
return a > b ? a : b;
}
int e() {
return -1;
}
void main_() {
int n, m;
while (std::cin >> n >> m, !(n == 0 && m == 0)) {
std::vector<std::pair<int, int>> ab(m);
std::vector<int> s(m);
rep(i, 0, m) {
auto& [a, b] = ab[i];
std::cin >> a >> b >> s[i];
a--;
b--;
}
std::vector<int> idx(m);
std::iota(all(idx), 0);
std::sort(all(idx), [&](int i, int j) -> bool { return s[i] > s[j]; });
undo_unionfind uf(n);
std::vector table(sz, std::vector<int>());
for (auto i : idx) {
auto [a, b] = ab[i];
uf.merge(a, b);
table[s[i]].emplace_back(i);
}
segtree<int, op, e> seg(n);
rep(i, 0, n) {
if (uf.par[i] < 0) {
seg.set(i, -uf.par[i]);
}
}
std::vector<int> ret(n, 1);
rep(i, 0, sz) {
std::vector<int> vs;
std::reverse(all(table[i]));
for (auto id : table[i]) {
auto [a, b] = ab[id];
if (ret[uf.leader(a)] < 0) {
uf.undo();
a = uf.leader(a);
b = uf.leader(b);
ret[a] = -1;
ret[b] = -1;
continue;
}
seg.set(uf.leader(a), -1);
uf.undo();
a = uf.leader(a);
b = uf.leader(b);
seg.set(a, uf.size(a));
seg.set(b, uf.size(b));
vs.emplace_back(a);
vs.emplace_back(b);
}
int max = seg.all_prod();
for (auto v : vs) {
v = uf.leader(v);
if (uf.size(v) < max) {
seg.set(v, -1);
ret[v] = -1;
}
}
}
std::vector<int> ans;
rep(i, 0, n) if (ret[i] > 0) {
ans.emplace_back(i + 1);
}
std::cout << ans << '\n';
}
}
} // namespace ebi
int main() {
ebi::main_();
}