Submission #1003147

#TimeUsernameProblemLanguageResultExecution timeMemory
1003147vjudge1Subtree (INOI20_subtree)C++17
8 / 100
119 ms2904 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10; vector<int> g[N]; struct DSU { vector<int> e; DSU(int n) { e=vector<int>(n+1, -1); } int get(int x) { if(e[x] < 0)return x; return e[x] = get(e[x]); } int sz(int x) { return -e[get(x)]; } bool unite(int a, int b) { a=get(a),b=get(b); if(a == b)return false; if(-e[a] > -e[b]) { swap(a,b); } e[b]+=e[a]; e[a] = b; return true; } }; int main () { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; for(int i = 0;i<m;i++) { int u, v; cin >> u >> v; u--,v--; g[u].push_back(v); } if(n <= 20) { int ans=0; for(int mask = 1;mask<(1<<n);mask++) { DSU d(n); int cnt=0; int f=-1, sz=0; for(int j = 0;j<n;j++) { if(mask&(1<<j)) { sz++; f=j; for(int to:g[j]){ if(mask&(1<<to)) { d.unite(to, j); cnt++; } } } } if(d.sz(f) == sz and cnt==sz-1){ ans++; } } cout << ans <<"\n"; } else { } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...