結果
| 問題 | No.2418 情報通だよ！Nafmoくん |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2023-08-12 13:49:56 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 2,000 ms |
| コード長 | 15,004 bytes |
| コンパイル時間 | 2,299 ms |
| コンパイル使用メモリ | 213,192 KB |
| 実行使用メモリ | 15,212 KB |
| 最終ジャッジ日時 | 2024-11-14 12:22:02 |
| 合計ジャッジ時間 | 3,647 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 35 ms
13,820 KB |
| testcase_04 | AC | 19 ms
12,400 KB |
| testcase_05 | AC | 19 ms
7,040 KB |
| testcase_06 | AC | 28 ms
13,144 KB |
| testcase_07 | AC | 20 ms
6,820 KB |
| testcase_08 | AC | 31 ms
15,212 KB |
| testcase_09 | AC | 25 ms
7,936 KB |
| testcase_10 | AC | 34 ms
12,520 KB |
| testcase_11 | AC | 32 ms
11,776 KB |
| testcase_12 | AC | 23 ms
10,368 KB |
| testcase_13 | AC | 12 ms
6,820 KB |
| testcase_14 | AC | 20 ms
8,448 KB |
| testcase_15 | AC | 15 ms
6,816 KB |
| testcase_16 | AC | 29 ms
10,080 KB |
| testcase_17 | AC | 9 ms
6,820 KB |
| testcase_18 | AC | 24 ms
11,520 KB |
| testcase_19 | AC | 16 ms
11,776 KB |
| testcase_20 | AC | 16 ms
6,820 KB |
| testcase_21 | AC | 13 ms
6,816 KB |
| testcase_22 | AC | 11 ms
6,816 KB |
| testcase_23 | AC | 2 ms
6,816 KB |
ソースコード
#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 2 "template.cpp"
#pragma region templates
#pragma region std::vector operator
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;
}
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 ios
namespace 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 submodule
void 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 scanner
template <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 printer
namespace 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 functions
template <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 vars
using 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 problems
struct 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: parent
std::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);
}