Submission #656171

#	Time	Username	Problem	Language	Result	Execution time	Memory
656171		Dorost	Port Facility (JOI17_port_facility)	C++17	22 / 100	64 ms	17956 KiB

port_facility

/* 	* 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;
}

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