Submission #418598

#	Time	Username	Problem	Language	Result	Execution time	Memory
418598		parsabahrami	Subtree (INOI20_subtree)	C++17	0 / 100	1 ms	204 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e6 + 10, MOD = 1e9 + 7;
int M[N]; int msk;

void DFS(vector<vector<int>> &adj, int v) {
	M[v] = 1;
	for (int u : adj[v]) 
		if (!M[u]) DFS(adj, u);
}

int check(vector<vector<int>> &adj, int n) {
	for (int i = 0; i < n; i++) 
		M[i] = 0;
	int rt = -1;
	for (int i = 0; i < n; i++) 
		if (msk & (1 << i)) rt = i;
	DFS(adj, rt);
	for (int i = 0; i < n; i++) 
		if ((msk & (1 << i)) && !M[i]) return 0;
	return 1;
}

vector<pii> E;
int n, m; vector<vector<int>> adj;

int main() {
	int cnt = 0;                                                                                                                           
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) 
		adj.push_back({});
	for (int i = 1; i <= m; i++) {
		int u, v; scanf("%d%d", &u, &v);
		u--, v--;
		E.push_back({u, v});
	}
	for (int i = 1; i < (1 << n) - 1; i++) {
		vector<pii> te; msk = i;
		for (pii &e : E)
			if (i & (1 << e.F)) {
				if (i & (1 << e.S)) te.push_back(e);
			}
		if (SZ(te) != __builtin_popcount(i) - 1) continue;
		for (int j = 0; j < n; j++) 
			adj[j] = {};
		for (pii &e : te) {
			adj[e.F].push_back(e.S);
			adj[e.S].push_back(e.F);
		}
		cnt += check(adj, n);
	}
	cout << cnt << endl;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:42:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~

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