제출 #1003147

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

Main

#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 {

  }
}

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