제출 #1003138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003138		vjudge1	Subtree (INOI20_subtree)	C++17	8 / 100	2037 ms	2904 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 1e5 + 5;
const int LOG = 20;
const int mod = 1e9 + 7;

vector<int> adj[MXN];
int msk, cyc, c;
int col[MXN], par[MXN];

void dfs(int a)
{
	c++;
	col[a] = 1;
	for (int v : adj[a])
	{
		if (!(msk >> v & 1)) continue;
		if (v == par[a]) continue;
		if (col[v] == 1) cyc = 1;
		if (!col[v]) 
		{
			par[v] = a;
			dfs(v);
		}
	}
	col[a] = 2;
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
  {
    int u, v;
    cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
  }
	int res = 0;
	for (msk = 1; msk < (1LL << n); msk++)
	{
		c = 0, cyc = 0;
		for (int i = 0; i < n; i++)
		{
			if (msk >> i & 1)
			{
				dfs(i);
				break;
			}
		}
		for (int i = 0; i < n; i++) par[i] = 0, col[i] = 0;
		if (c == __builtin_popcount(msk) && !cyc) res++;
	}
	cout << res << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50