結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
![]() |
提出日時 | 2023-08-12 13:53:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 2,397 bytes |
コンパイル時間 | 888 ms |
コンパイル使用メモリ | 88,888 KB |
実行使用メモリ | 30,440 KB |
最終ジャッジ日時 | 2024-11-14 12:22:28 |
合計ジャッジ時間 | 2,852 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>#include <map>using namespace std;/*#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;*/#define all(x) (x).begin(),(x).end()#define rep(i, n) for (int i = 0; i < (n); i++)#define endl "\n"#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")typedef long long ll;typedef pair<int, int> pii;typedef pair<ll, ll> pll;template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]";return os;}template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }const int mod = 1e9 + 7;struct UnionFind {vector<int> data;int gnum;UnionFind(int size) : data(size, -1), gnum(size) {}bool unionSet(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;gnum--;}return x != y;}bool findSet(int x, int y) {return root(x) == root(y);}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}int getGroupNum() {return gnum;}vector<vector<int>> getGroups() {map<int, vector<int>> G;int N = data.size();for (int i = 0; i < N; i++) {G[root(i)].push_back(i);}vector<vector<int>> ret;for(auto g : G) {ret.push_back(g.second);}return ret;}};void solve() {int N, M; cin >> N >> M; N *= 2;UnionFind uf(N);for (int i = 0; i < M; i++) {int a, b; cin >> a >> b; a--, b--;uf.unionSet(a, b);}vector<vector<int>> G = uf.getGroups();int cnt = 0;for (int i = 0; i < G.size(); i++) {if (G[i].size() % 2 == 1) cnt++;}cout << cnt / 2 << endl;}int main() {#ifdef LOCAL_ENVcin.exceptions(ios::failbit);#endifcin.tie(0);ios::sync_with_stdio(false);cout.setf(ios::fixed);cout.precision(16);solve();}