結果
問題 | No.2418 情報通だよ!Nafmoくん |
ユーザー |
|
提出日時 | 2023-08-12 13:49:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 15,004 bytes |
コンパイル時間 | 2,025 ms |
コンパイル使用メモリ | 206,160 KB |
最終ジャッジ日時 | 2025-02-16 03:45:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#line 1 "main.cpp"#include <bits/stdc++.h>#line 2 "template.cpp"#pragma region templates#pragma region std::vector operatortemplate <class T>std::vector<T> &operator++(std::vector<T> &v) {for (auto &e : v) {++e;}return v;}template <class T>std::vector<T> operator++(std::vector<T> &v, int) {auto res = v;for (auto &e : v) {++e;}return res;}template <class T>std::vector<T> &operator--(std::vector<T> &v) {for (auto &e : v) {--e;}return v;}template <class T>std::vector<T> operator--(std::vector<T> &v, int) {auto res = v;for (auto &e : v) {--e;}return res;}#pragma endregion#pragma region iosnamespace scanner {namespace submodule {void read(int &a) {std::cin >> a;}void read(long long &a) {std::cin >> a;}void read(char &a) {std::cin >> a;}void read(double &a) {std::cin >> a;}void read(std::string &a) {std::cin >> a;}template <class T, class S>void read(std::pair<T, S> &p) {read(p.first);read(p.second);}template <class T>void read(std::vector<T> &);template <class T>void read(std::vector<T> &a) {for (auto &e : a) {read(e);}}template <class T>void read(T &a) {std::cin >> a;}} // namespace submodulevoid scan() {}template <class Head, class... Tail>void scan(Head &head, Tail &...tail) {submodule::read(head);scan(tail...);}void scanI() {}template <class Head, class... Tail>void scanI(Head &head, Tail &...tail) {submodule::read(head);--head;scanI(tail...);}} // namespace scannertemplate <class T, class U>std::ostream &operator<<(std::ostream &os, std::pair<T, U> pa) {os << '{' << pa.first << ", " << pa.second << '}';return os;}template <class T>std::ostream &operator<<(std::ostream &os, std::vector<T> vec) {os << "{";const int n = (int)vec.size();for (int i = 0; i < n; i++) {os << vec[i];os << (i == n - 1 ? "}" : ", ");}return os;}template <class T, std::size_t S>std::ostream &operator<<(std::ostream &os, std::array<T, S> arr) {os << "{";for (int i = 0; i < (int)S; i++) {os << arr[i];os << (i == S - 1 ? "}" : ", ");}os << "}";return os;}template <class T, class U>std::ostream &operator<<(std::ostream &os, std::map<T, U> ma) {os << "{";auto itr = ma.begin();while (itr != ma.end()) {os << *itr << (itr == --ma.end() ? "}" : ", ");++itr;}return os;}template <class T>std::ostream &operator<<(std::ostream &os, std::set<T> st) {os << "{";auto itr = st.begin();while (itr != st.end()) {os << *itr << (itr == --st.end() ? "}" : ", ");++itr;}return os;}namespace printer {void print() {std::cout << '\n';}template <class Head, class... Tail>void print(const Head &head, const Tail &...tail) {std::cout << head;if (sizeof...(tail))std::cout << ' ';print(tail...);}} // namespace printernamespace dumper {void dumpFunc() {std::cerr << std::endl;}template <class Head, class... Tail>void dumpFunc(Head &&head, Tail &&...tail) {std::cerr << head;if (sizeof...(Tail) == 0) {std::cerr << ' ';} else {std::cerr << ", ";}dumpFunc(std::move(tail)...);}} // namespace dumper#pragma endregion#pragma region functionstemplate <class T>constexpr int si(const T &c) {return static_cast<int>(c.size());}template <class T>constexpr bool afMin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <class T>constexpr bool afMax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T = long long, class S>constexpr T calcSum(const S &container) {return std::accumulate(container.begin(), container.end(), static_cast<T>(0));}template <class T>constexpr auto calcMin(const T &container) {return *std::min_element(container.begin(), container.end());}template <class T>constexpr auto calcMax(const T &container) {return *std::max_element(container.begin(), container.end());}template <class T>constexpr int lwbi(const T &container, const typename T::value_type &value) {return static_cast<int>(std::distance(container.cbegin(), std::lower_bound(container.cbegin(), container.cend(), value)));}template <class T>constexpr int upbi(const T &container, const typename T::value_type &value) {return static_cast<int>(std::distance(container.cbegin(), std::upper_bound(container.cbegin(), container.cend(), value)));}template <class T>auto makeVec(const int n, const T &value) {return std::vector(n, value);}template <class... Args>auto makeVec(const int n, Args... args) {return std::vector(n, makeVec(args...));}template <class T, class F>T binarySearch(T ok, T ng, const F &f) {while (abs(ok - ng) > 1) {T mid = ok + ng >> 1;(f(mid) ? ok : ng) = mid;}return ok;}template <class T, class F>T binarySearchReal(T ok, T ng, const F &f, int iter = 80) {while (iter--) {T mid = (ok + ng) / 2;(f(mid) ? ok : ng) = mid;}return ok;}#pragma endregion#pragma region macros and varsusing namespace scanner;using namespace printer;using i64 = long long;template <class T>using Vec = std::vector<T>;template <class T>using PQ = std::priority_queue<T>;template <class T>using RPQ = std::priority_queue<T, std::vector<T>, std::greater<T>>;std::mt19937 mtRand(std::random_device{}());constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};constexpr std::array<std::pair<int, int>, 8> dxy8 = {{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};#define INT(...) \int __VA_ARGS__; \scan(__VA_ARGS__)#define INTI(...) \int __VA_ARGS__; \scanI(__VA_ARGS__)#define I64(...) \i64 __VA_ARGS__; \scan(__VA_ARGS__)#define I64I(...) \i64 __VA_ARGS__; \scanI(__VA_ARGS__)#define STR(...) \std::string __VA_ARGS__; \scan(__VA_ARGS__)#define CHR(...) \char __VA_ARGS__; \scan(__VA_ARGS__)#define DOUBLE(...) \double __VA_ARGS__; \scan(__VA_ARGS__)#define VEC(type, name, n) \std::vector<type> name(n); \scan(name)#define VECI(type, name, n) \std::vector<type> name(n); \scanI(name)#define VEC2(type, name1, name2, n) \std::vector<type> name1(n), name2(n); \for (int i = 0; i < n; i++) \scan(name1[i], name2[i])#define VEC2I(type, name1, name2, n) \std::vector<type> name1(n), name2(n); \for (int i = 0; i < n; i++) \scanI(name1[i], name2[i])#define VEC3(type, name1, name2, name3, n) \std::vector<type> name1(n), name2(n), name3(n); \for (int i = 0; i < n; i++) \scan(name1[i], name2[i], name3[i])#define VEC3I(type, name1, name2, name3, n) \std::vector<type> name1(n), name2(n), name3(n); \for (int i = 0; i < n; i++) \scanI(name1[i], name2[i], name3[i])#define VEC4(type, name1, name2, name3, name4, n) \std::vector<type> name1(n), name2(n), name3(n), name4(n); \for (int i = 0; i < n; i++) \scan(name1[i], name2[i], name3[i], name4[i]);#define VEC4I(type, name1, name2, name3, name4, n) \std::vector<type> name1(n), name2(n), name3(n), name4(n); \for (int i = 0; i < n; i++) \scanI(name1[i], name2[i], name3[i], name4[i]);#define VV(type, name, h, w) \std::vector<std::vector<type>> name(h, std::vector<type>(w)); \scan(name)#define VVI(type, name, h, w) \std::vector<std::vector<type>> name(h, std::vector<type>(w)); \scanI(name)#define overload5(a, b, c, d, e, name, ...) name#define rep(i, l, r) for (int i = (l); i < (r); ++i)#define per(i, l, r) for (int i = (r - 1); i >= (l); --i)#define fore0(a) rep (a.size())#define fore1(i, a) for (auto &&i : a)#define fore2(a, b, v) for (auto &&[a, b] : v)#define fore3(a, b, c, v) for (auto &&[a, b, c] : v)#define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v)#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)#define pb push_back#define eb emplace_back#define mp std::make_pair#define ALL(x) (x).begin(), (x).end()#define UNIQUE(x) (x).erase(std::unique((x).begin(), (x).end()), (x).end())#define fi first#define se second#define dump(...) \std::cerr << ' '; \std::cerr << #__VA_ARGS__ << " : [" << __LINE__ << " : " << __FUNCTION__ << "]" << std::endl; \std::cerr << " "; \dumper::dumpFunc(__VA_ARGS__)#pragma endregion#pragma endregion#line 4 "main.cpp"#line 1 "/Library/atcoder/dsu.hpp"#line 7 "/Library/atcoder/dsu.hpp"namespace atcoder {// Implement (union by size) + (path compression)// Reference:// Zvi Galil and Giuseppe F. Italiano,// Data structures and algorithms for disjoint set union problemsstruct dsu {public:dsu() : _n(0) {}explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}int merge(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);int x = leader(a), y = leader(b);if (x == y) return x;if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);parent_or_size[x] += parent_or_size[y];parent_or_size[y] = x;return x;}bool same(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return leader(a) == leader(b);}int leader(int a) {assert(0 <= a && a < _n);if (parent_or_size[a] < 0) return a;return parent_or_size[a] = leader(parent_or_size[a]);}int size(int a) {assert(0 <= a && a < _n);return -parent_or_size[leader(a)];}std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(_n), group_size(_n);for (int i = 0; i < _n; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(_n);for (int i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}private:int _n;// root node: -1 * component size// otherwise: parentstd::vector<int> parent_or_size;};} // namespace atcoder#line 6 "main.cpp"struct MakeIOFast {MakeIOFast() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(15);}} makeIOFastv;using namespace std;int main() {INT(N, M);VEC2I(int, A, B, M);atcoder::dsu uft(2 * N);rep (i, 0, M) uft.merge(A[i], B[i]);int cnt = 0;const auto g = uft.groups();for (const auto &e : g) {if (e.size() % 2 == 1) ++cnt;}print(cnt / 2);}