結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-07-11 13:22:40 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 1,955 ms |
コンパイル使用メモリ | 127,488 KB |
実行使用メモリ | 20,096 KB |
最終ジャッジ日時 | 2024-11-14 12:20:01 |
合計ジャッジ時間 | 4,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <cassert> #include <map> #include <vector> using namespace std; struct UnionFind { vector<int> data; const uint __size; UnionFind(const int size = 0) noexcept : data(size, -1), __size(max(0, size)) {} inline int root(const int& x) { assert((uint)x < __size); if (data[x] < 0) return x; return data[x] = root(data[x]); } inline bool unite(const int& x, const int& y) { int rx = root(x), ry = root(y); if (rx == ry) return false; if (data[rx] > data[ry]) swap(rx, ry); data[rx] += data[ry]; data[ry] = rx; return true; } inline bool same(const int& x, const int& y) { return root(x) == root(y); } inline int size(const int& x) { return -data[root(x)]; } }; int main() { int n, m; cin >> n >> m; assert(1 <= n && n <= 100000); assert(0 <= m && m <= 100000); UnionFind uf(2 * n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; assert(1 <= a && a <= 2 * n); assert(1 <= b && b <= 2 * n); a -= 1; b -= 1; uf.unite(a, b); } map<int, vector<int>> group; for (int i = 0; i < 2 * n; ++i) { group[uf.root(i)].push_back(i); } int ans = 0; for (auto [_, g] : group) { if (g.size() % 2) { ans += 1; } } cout << ans / 2 << endl; return 0; }