Submission #1400694
Source Code Expand
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef vector<ll> VL; typedef pair<int, int> PI; /* * Union-Find tree * header requirement: vector */ class UnionFind { private: std::vector<int> disj; std::vector<int> rank; public: UnionFind(int n) : disj(n), rank(n) { for (int i = 0; i < n; ++i) { disj[i] = i; rank[i] = 0; } } int root(int x) { if (disj[x] == x) { return x; } return disj[x] = root(disj[x]); } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) { return; } if (rank[x] < rank[y]) { disj[x] = y; } else { disj[y] = x; if (rank[x] == rank[y]) { ++rank[x]; } } } bool is_same_set(int x, int y) { return root(x) == root(y); } }; int main(void){ int n, m; cin >> n >> m; vector<VI> edges(n); REP(i, 0, m) { int x, y; cin >> x >> y; x--, y--; edges[x].push_back(y); edges[y].push_back(x); } // Try all possibilities to make G a bipartite graph int tot = 0; REP(bits, 0, 1 << n) { // Construct UnionFind uf(n); int conn = n; REP(i, 0, n) { if ((bits & 1 << i) == 0) { continue; } REP(j, 0, edges[i].size()) { int w = edges[i][j]; if (bits & 1 << w) { continue; } if (not uf.is_same_set(i, w)) { uf.unite(i, w); conn -= 1; } } } // Are all degrees of vertices in this subgraph >0? // Is this subgraph connected? if (conn == 1) { tot += 1; } } cout << tot / 2 << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - Orange Graph |
User | kobae964 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2030 Byte |
Status | AC |
Exec Time | 63 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
test_01.txt | AC | 1 ms | 256 KB |
test_02.txt | AC | 1 ms | 256 KB |
test_03.txt | AC | 17 ms | 256 KB |
test_04.txt | AC | 9 ms | 256 KB |
test_05.txt | AC | 17 ms | 256 KB |
test_06.txt | AC | 9 ms | 256 KB |
test_07.txt | AC | 37 ms | 256 KB |
test_08.txt | AC | 17 ms | 256 KB |
test_09.txt | AC | 58 ms | 256 KB |
test_10.txt | AC | 27 ms | 256 KB |
test_11.txt | AC | 43 ms | 256 KB |
test_12.txt | AC | 21 ms | 256 KB |
test_13.txt | AC | 48 ms | 256 KB |
test_14.txt | AC | 23 ms | 256 KB |
test_15.txt | AC | 53 ms | 256 KB |
test_16.txt | AC | 24 ms | 256 KB |
test_17.txt | AC | 57 ms | 256 KB |
test_18.txt | AC | 27 ms | 256 KB |
test_19.txt | AC | 63 ms | 256 KB |
test_20.txt | AC | 29 ms | 256 KB |