oj.uz

Submission #418598

# Submission time Handle Problem Language Result Execution time Memory
418598 2021-06-05T15:20:04 Z parsabahrami Subtree (INOI20_subtree) C++17
0 / 100
 1 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -