# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
418599 | parsabahrami | Subtree (INOI20_subtree) | C++17 | 245 ms | 588 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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); 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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |