Submission #3016280
Source Code Expand
#include <cassert> #include <utility> template <template <class> class Container> class union_find { protected: class node_type; public: using container_type = Container<node_type>; using size_type = typename container_type::size_type; protected: class node_type { public: size_type parent; size_type size; }; container_type tree; public: union_find() : tree() {} explicit union_find(const size_type size) : tree(size, { 0, 1 }) { for (size_type i = 0; i < size; ++i) tree[i].parent = i; } bool empty() const { return tree.empty(); } size_type size() const { return tree.size(); } size_type find(size_type x) { assert(x < size()); while (tree[x].parent != x) x = tree[x].parent = tree[tree[x].parent].parent; return x; } bool same(const size_type x, const size_type y) { assert(x < size()); assert(y < size()); return find(x) == find(y); } size_type size(const size_type x) { assert(x < size()); return tree[find(x)].size; } ::std::pair<size_type, size_type> unite(size_type x, size_type y) { assert(x < size()); assert(y < size()); x = find(x); y = find(y); if (x != y) { if (tree[x].size < tree[y].size) ::std::swap(x, y); tree[x].size += tree[y].size; tree[y].parent = x; } return { x, y }; } }; #include<iostream> #include<cstdint> #include<vector> template<class T> using vec_alias = ::std::vector<T>; int main() { using u32 = ::std::uint_fast32_t; using u64 = ::std::uint_fast64_t; u32 n, m; ::std::cin >> n >> m; union_find<vec_alias> uf(n * 2); for (u32 i = 0;i < m;++i) { u32 a, b; ::std::cin >> a >> b; --a; --b; uf.unite(a, b + n); uf.unite(a + n, b); } if (uf.same(0, n)) { ::std::cout << static_cast<u64>(n)*(n - 1) / 2 - m << ::std::endl; return 0; } u64 cnt = 0; for (u32 i = 0;i < n;++i) if (uf.same(0, i)) ++cnt; ::std::cout << (static_cast<u64>(n) - cnt) * cnt - m << ::std::endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 3 Steps |
User | noshi91 |
Language | C++14 (GCC 5.4.1) |
Score | 500 |
Code Size | 2032 Byte |
Status | AC |
Exec Time | 64 ms |
Memory | 3328 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
all | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | AC | 1 ms | 256 KB |
01-06.txt | AC | 2 ms | 256 KB |
01-07.txt | AC | 1 ms | 256 KB |
01-08.txt | AC | 1 ms | 256 KB |
01-09.txt | AC | 2 ms | 256 KB |
01-10.txt | AC | 3 ms | 256 KB |
02-01.txt | AC | 61 ms | 3072 KB |
02-02.txt | AC | 64 ms | 3328 KB |
02-03.txt | AC | 59 ms | 3328 KB |
02-04.txt | AC | 60 ms | 3328 KB |
02-05.txt | AC | 64 ms | 3328 KB |
02-06.txt | AC | 63 ms | 3328 KB |
02-07.txt | AC | 57 ms | 1792 KB |
02-08.txt | AC | 63 ms | 3072 KB |
02-09.txt | AC | 63 ms | 3328 KB |
02-10.txt | AC | 42 ms | 256 KB |
02-11.txt | AC | 48 ms | 512 KB |
02-12.txt | AC | 57 ms | 1792 KB |
02-13.txt | AC | 59 ms | 2688 KB |
02-14.txt | AC | 60 ms | 3328 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |