Submission #1357686
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;
struct UnionFind{
vector<int> par,rank;
UnionFind(int n) :par(n + 1),rank(n + 1,1){
for(int i = 1;i <= n;i++) par [i] = i;
}
int find(int x){
return par [x] == x ? x : par [x] = find(par [x]);
}
bool unite(int x,int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(rank [x] < rank [y]) swap(x,y);
rank [x] += rank [x] == rank [y];
par [y] = x;
return true;
}
bool same(int x,int y){
return find(x) == find(y);
}
};
int N,M;
const int MAX_N = 16;
bool G [MAX_N] [MAX_N];
int main()
{
scanf("%d%d",&N,&M);
FOR(i,0,M){
int u,v;
scanf("%d%d",&u,&v);
G [u - 1] [v - 1] = true;
G [v - 1] [u - 1] = true;
}
int ans = 0;
FOR(mask,0,1 << N){
int cnt = 1;
UnionFind uf(N);
FOR(i,0,N) FOR(j,0,N) if((mask >> i & 1) ^ (mask >> j & 1)){
if(G [i] [j]){
cnt += uf.unite(i,j);
}
}
ans += cnt == N;
}
ans /= 2;
printf("%d\n",ans);
return 0;
}
Submission Info
Submission Time
2017-06-17 15:11:31+0900
Task
C - Orange Graph
User
gigime
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1275 Byte
Status
AC
Exec Time
100 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:37:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&N,&M);
^
./Main.cpp:40:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^
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
67 ms
256 KB
test_04.txt
AC
32 ms
256 KB
test_05.txt
AC
68 ms
256 KB
test_06.txt
AC
32 ms
256 KB
test_07.txt
AC
75 ms
256 KB
test_08.txt
AC
35 ms
256 KB
test_09.txt
AC
83 ms
256 KB
test_10.txt
AC
39 ms
256 KB
test_11.txt
AC
100 ms
256 KB
test_12.txt
AC
44 ms
256 KB
test_13.txt
AC
98 ms
256 KB
test_14.txt
AC
46 ms
256 KB
test_15.txt
AC
98 ms
256 KB
test_16.txt
AC
46 ms
256 KB
test_17.txt
AC
96 ms
256 KB
test_18.txt
AC
44 ms
256 KB
test_19.txt
AC
88 ms
256 KB
test_20.txt
AC
41 ms
256 KB