Submission #1521664


Source Code Expand

#include<iostream>
#include<vector>
#include<map>
using namespace std;
vector<int>x[17]; int n, m, a[125], b[125], cnt, d[17]; map<long long, int>M;
void dfs(int pos, int depth) {
	if (d[pos] != -1)return;
	d[pos] = depth;
	for (int i = 0; i < x[pos].size(); i++)dfs(x[pos][i], depth ^ 1);
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; }
	for (int i = 0; i < (1 << n); i++) {
		int bit[17]; for (int j = 0; j < n; j++)bit[j] = (i / (1 << j)) % 2;
		long long p = 0, q = 1, mod = 1145141919810893LL;
		for (int j = 0; j < n; j++)x[j].clear();
		for (int j = 0; j < m; j++) {
			if (bit[a[j]] != bit[b[j]]) { p += q; x[a[j]].push_back(b[j]); x[b[j]].push_back(a[j]); }
			p %= mod; q *= 2; q %= mod;
		}
		for (int j = 0; j < n; j++)d[j] = -1;
		dfs(0, 0);
		bool OK = false;
		for (int j = 0; j < m; j++) {
			if (bit[a[j]] == bit[b[j]] && d[a[j]] != d[b[j]]) OK = true;
		}
		if (M[p] == 0 && OK == false) {
			cnt++; M[p] = 1;
		}
	}
	cout << cnt << endl;
	return 0;
}

Submission Info

Submission Time
Task C - Orange Graph
User E869120
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1055 Byte
Status AC
Exec Time 159 ms
Memory 2304 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 23
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 28 ms 2304 KB
test_04.txt AC 14 ms 1280 KB
test_05.txt AC 30 ms 2304 KB
test_06.txt AC 15 ms 1280 KB
test_07.txt AC 50 ms 2304 KB
test_08.txt AC 24 ms 1280 KB
test_09.txt AC 107 ms 2304 KB
test_10.txt AC 49 ms 1280 KB
test_11.txt AC 103 ms 2304 KB
test_12.txt AC 50 ms 1280 KB
test_13.txt AC 116 ms 2304 KB
test_14.txt AC 53 ms 1280 KB
test_15.txt AC 133 ms 2304 KB
test_16.txt AC 58 ms 1280 KB
test_17.txt AC 145 ms 2304 KB
test_18.txt AC 67 ms 1280 KB
test_19.txt AC 159 ms 2304 KB
test_20.txt AC 70 ms 1280 KB