제출 #656171

#제출 시각아이디문제언어결과실행 시간메모리
656171DorostPort Facility (JOI17_port_facility)C++17
22 / 100
64 ms17956 KiB
/* 	* In the name of GOD  */

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
#define F first
#define S second
#define mk make_pair
const int N = 2012, M = 1000 * 1000 * 1000 + 7;
pii a[N];
bool c[N], f = true, vis[N];
vector <int> g[N];

void dfs(int v) {
	vis[v] = true;
	for (auto u : g[v]) {
		if (!vis[u]) {
			c[u] = !c[v];
			dfs(u);
		} else {
			if (c[u] == c[v])
				f = false;
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i].F >> a[i].S;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (a[i].F < a[j].F && a[i].S > a[j].F && a[i].S < a[j].S) {
				g[i].push_back(j);
				g[j].push_back(i);
			}
	int com = 0;
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			com++;
			dfs(i);
		}
	}
	int ans = f;
	for (int i = 0; i < com; i++) {
		ans *= 2;
		if (ans >= M)
			ans -= M;
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...