結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-08-12 13:48:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 2,617 bytes |
コンパイル時間 | 1,646 ms |
コンパイル使用メモリ | 175,164 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-11-14 12:21:54 |
合計ジャッジ時間 | 3,644 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>/// @brief Union-Find 木/// @note 1.4 高速化 + 省メモリ化/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-findclass UnionFind{public:UnionFind() = default;/// @brief Union-Find 木を構築します。/// @param n 要素数explicit UnionFind(size_t n): m_parentsOrSize(n, -1) {}/// @brief 頂点 i の root のインデックスを返します。/// @param i 調べる頂点のインデックス/// @return 頂点 i の root のインデックスint find(int i){if (m_parentsOrSize[i] < 0){return i;}// 経路圧縮return (m_parentsOrSize[i] = find(m_parentsOrSize[i]));}/// @brief a のグループと b のグループを統合します。/// @param a 一方のインデックス/// @param b 他方のインデックスvoid merge(int a, int b){a = find(a);b = find(b);if (a != b){// union by size (小さいほうが子になる)if (-m_parentsOrSize[a] < -m_parentsOrSize[b]){std::swap(a, b);}m_parentsOrSize[a] += m_parentsOrSize[b];m_parentsOrSize[b] = a;}}/// @brief a と b が同じグループに属すかを返します。/// @param a 一方のインデックス/// @param b 他方のインデックス/// @return a と b が同じグループに属す場合 true, それ以外の場合は falsebool connected(int a, int b){return (find(a) == find(b));}/// @brief i が属するグループの要素数を返します。/// @param i インデックス/// @return i が属するグループの要素数int size(int i){return -m_parentsOrSize[find(i)];}private:// m_parentsOrSize[i] は i の 親,// ただし root の場合は (-1 * そのグループに属する要素数)std::vector<int> m_parentsOrSize;};using namespace std;typedef long long ll;#define rep(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)#define rrep(i,a,b) for(ll i=(ll)(a-1);i>=(ll)(b);i--)#define MOD 998244353//#define MOD 1e9+7#define INF 1e16//#define PI numbers::pi//#define E numbers::etemplate <typename T> bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template <typename T> bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}int main(){ll n,m; cin >> n >> m;ll ans=0;UnionFind uf(2*n);set<ll> st;rep(i,0,m){ll a,b; cin >> a >> b;a--,b--;uf.merge(a,b);}rep(i,0,2*n){if(!st.count(uf.find(i))&&uf.size(i)%2==1){ans++;st.insert(uf.find(i));}}cout << ans/2 << endl;}