結果
問題 | No.583 鉄道同好会 |
ユーザー |
|
提出日時 | 2024-07-17 02:46:10 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 2,989 bytes |
コンパイル時間 | 1,022 ms |
コンパイル使用メモリ | 98,212 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-17 02:46:14 |
合計ジャッジ時間 | 2,316 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 |
ソースコード
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/0225#include <iostream>#include <set>template <class T>struct flip_set {flip_set() : data() {}const auto begin() const { return data.begin(); }auto begin() { return data.begin(); }const auto end() const { return data.end(); }auto end() { return data.end(); }bool empty() const { return data.empty(); }int size() const { return data.size(); }bool contains(const T &x) const { return data.count(x); }bool contains(T &&x) const { return data.count(std::move(x)); }bool flip(const T &x) {if (data.count(x)) return data.erase(x), false;else return data.emplace(x), true;}bool flip(T &&x) {if (data.count(x)) return data.erase(std::move(x)), false;else return data.emplace(x), true;}private:std::set<T> data;};#include <utility>#include <vector>/*** @brief 素集合データ構造* @details Implement (union by size) + (path compression)* @see https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp*/struct union_find {union_find() = default;explicit union_find(int _n) : _rank(_n), data(_n, -1) {}const int &operator[](std::size_t x) const { return data[x]; }int &operator[](std::size_t x) { return data[x]; }int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }int get_root(int x) { return root(x); }bool is_root(int x) const { return data[x] < 0; }bool same(int x, int y) { return root(x) == root(y); }bool is_same(int x, int y) { return same(x, y); }int rank() { return _rank; }int size(int x) { return -(data[root(x)]); }int get_size(int x) { return size(x); }std::vector<int> leaders() {std::vector<int> res;for (int i = 0; i < (int)data.size(); ++i) {if (is_root(i)) res.emplace_back(i);}return res;}bool unite(int x, int y) {x = root(x), y = root(y);if (x == y) return false;--_rank;if (data[x] > data[y]) std::swap(x, y);data[x] += data[y];data[y] = x;return true;}template <class F>bool unite(int x, int y, F f) {x = root(x), y = root(y);if (x != y) {if (data[x] > data[y]) std::swap(x, y);data[x] += data[y];data[y] = x;}f(x, y);return x != y;}private:int _rank;std::vector<int> data;};int main(void) {int n, m;std::cin >> n >> m;flip_set<int> fs;std::set<int> st;union_find uf(n);while (m--) {int a, b;std::cin >> a >> b;fs.flip(a);fs.flip(b);st.emplace(a);st.emplace(b);uf.unite(a, b);}if (uf.size(*st.begin()) == (int)st.size() && fs.size() <= 2) {std::cout << "YES\n";} else {std::cout << "NO\n";}return 0;}