test/aoj/aoj_1645.test.cpp

View this file on GitHub
Last update: 2023-10-31 01:04:45+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_();
}