제출 #168688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168688		maruii	Port Facility (JOI17_port_facility)	C++14	22 / 100	57 ms	16636 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
using pii = pair<int, int>;

pii P[2002];

const int mod = 1e9 + 7;
int mp(int x, int a) {
	if (a == 0) return 1;
	int ret = mp(x, a >> 1);
	if (a & 1) return 1ll * ret * ret % mod * x % mod;
	return 1ll * ret * ret % mod;
}

bool vis[2002], C[2002];
vector<int> edge[2002];
bool dfs(int x) {
	vis[x] = 1;
	for (auto i : edge[x]) {
		if (vis[i]) {
			if (C[x] == C[i]) return 1;
			continue;
		}
		C[i] = C[x] ^ 1;
		if (dfs(i)) return 1;
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; ++i) {
		int x, y; cin >> x >> y;
		P[i] = {x, y};
	}
	sort(P, P + N);
	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j) {
			if (P[j].ff < P[i].ss && P[i].ss < P[j].ss) edge[i].push_back(j), edge[j].push_back(i);
		}
	}
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		if (vis[i]) continue;
		if (dfs(i)) return !printf("0");
		cnt++;
	}
	printf("%d", mp(2, cnt));
	return 0;
}

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