Submission #1141274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141274		LucaLucaM	Port Facility (JOI17_port_facility)	C++17	22 / 100	6093 ms	40564 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 1e6;
const int mod = 1e9 + 7;

struct Container {
  int x, y;
  bool operator < (const Container &other) const {
    return x != other.x? x < other.x : y < other.y;
  };
};

Container a[NMAX + 1];

std::vector<int> g[NMAX + 1];
bool vis[NMAX + 1];
int color[NMAX + 1];
bool bad = false;

void dfs(int u) {
  vis[u] = true;
  for (const auto &v : g[u]) {
    if (!vis[v]) {
      color[v] = (color[u] ^ 1);
      dfs(v);
    } else {
      if (color[u] == color[v]) {
        bad = true;
      }
    }
  }
}

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i].x >> a[i].y;
  }

  std::sort(a + 1, a + n + 1);

  for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (a[i].y > a[j].x && a[i].y < a[j].y) {
        g[i].push_back(j);
        g[j].push_back(i);
      }
    }
  }

  int answer = 1;

  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      color[i] = 0;
      dfs(i);
      if (bad) {
        std::cout << 0;
        return 0;
      }
      answer = (2 * answer) % mod;
    }
  }


  std::cout << answer;

  return 0;
} 

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