Submission #945700

#	Time	Username	Problem	Language	Result	Execution time	Memory
945700		vjudge1	Amusement Park (CEOI19_amusementpark)	C++17	19 / 100	3059 ms	592 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
  return a < b ? (a = b) == b : false;
}

bool check(vector<vector<int>> g) {
  int n = size(g);
  vector<bool> vis(n, false);
  vector<int> top_sort;
  function<void(int)> dfs = [&](int v) {
    vis[v] = true;
    for (int to : g[v]) {
      if (!vis[to]) dfs(to);
    }
    top_sort.push_back(v);
  };
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) dfs(i);
  }
  reverse(all(top_sort));
  int pos[n];
  for (int i = 0; i < n; ++i) {
    pos[top_sort[i]] = i;
  }
  for (int i = 0; i < n; ++i) {
    for (int to : g[i]) {
      if (pos[to] < pos[i]) return false;
    }
  }
  return true;
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m; cin >> n >> m;
  int a[m], b[m];
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }
  int res = 0;
  for (int mask = 0; mask < (1 << m); ++mask) {
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
      if (mask >> i & 1) {
        g[b[i]].push_back(a[i]);
      } else {
        g[a[i]].push_back(b[i]);
      }
    }
    if (check(g)) {
      res += __builtin_popcount(mask);
    }
  }
  cout << res;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37