Submission #655964

#	Time	Username	Problem	Language	Result	Execution time	Memory
655964		Behradm	Port Facility (JOI17_port_facility)	C++17	22 / 100	6043 ms	47872 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 f[N], pw[N], pos[2 * N], prf[N], suf[N], mk[N];
vector<int> g[N];

struct dsu {
  int n, cnt;
  vector<int> p, sz;

  dsu(int _n) : n(_n) {
    cnt = n;
    sz.assign(n, 1);
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  int get(int u) {
    return p[u] = (u == p[u] ? u : get(p[u]));
  }

  void merge(int u, int v) {
    u = get(u), v = get(v);
    if (u == v) return;
    if (sz[u] > sz[v]) swap(u, v);
    cnt--;

    p[u] = v;
    sz[v] += sz[u];
    sz[u] = 0;
  }
};

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;
  vector<pair<int, int>> x(n);
  for (int i = 0; i < n; i++)
    cin >> x[i].first >> x[i].second;
  sort(x.begin(), x.end());

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (x[i].first < x[j].first && x[j].first < x[i].second && x[i].second < x[j].second) {
        g[i].push_back(j);
        g[j].push_back(i);
      }
    }
  }

  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