Submission #656085

#	Time	Username	Problem	Language	Result	Execution time	Memory
656085		Behradm	Port Facility (JOI17_port_facility)	C++17	22 / 100	4946 ms	1048576 KiB

port_facility

/*\ In The Name Of GOD
 *  Beyrad :D
\*/
#include "bits/stdc++.h"

#define sz(x) ((int) (x).size())

using namespace std;

const int N = 1e6 + 11, mod = 1e9 + 7;
int pw[N], mk[N], f[2 * N];
bitset<2 * N> sf;
vector<int> g[N];

bool bad;
void dfs(int u, int c) {
  mk[u] = c;
  for (int v : g[u]) {
    if (mk[v] == -1)
      dfs(v, c ^ 1);
    else if (mk[v] == mk[u])
      bad = 1;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  memset(mk, -1, sizeof mk);
  pw[0] = 1;
  for (int i = 1; i < N; i++)
    pw[i] = pw[i - 1] * 2 % mod;

  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    sf[a] = 0, sf[b] = 1;
    f[a] = f[b] = i;
  }

  vector<int> st;
  for (int i = 0; i < 2 * n; i++) {
    if (sf[i] == 0) {
      st.push_back(f[i]);
    } else {
      vector<int> tmp;
      while (!st.empty() && st.back() != f[i]) {
        g[f[i]].push_back(st.back());
        g[st.back()].push_back(f[i]);
        tmp.push_back(st.back());
        st.pop_back();
      }
      st.pop_back();
      while (!tmp.empty())
        st.push_back(tmp.back()), tmp.pop_back();
    }
  }

  bad = 0;
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (mk[i] == -1)
      dfs(i, 0), cnt++;
  }
  if (bad) 
    return cout << 0 << '\n', 0;
  cout << pw[cnt] << '\n';
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22