제출 #656029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656029		Farbod	Port Facility (JOI17_port_facility)	C++17	22 / 100	36 ms	16460 KiB

port_facility

/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Sun, 06 Nov 2022 (12:21:23)
*
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 2005, mod = 1e9 + 7;

int n, l[N], r[N];
vector <int> adj[N];

int d[N];
queue <int> q;

long long p(int a, int r)
{
	if (r == 0)
		return 1;
	if (r == 1)
		return a;

	long long c = p(a, r / 2);
	return c * c % mod * p(a, r % 2) % mod;
}

bool f(int i, int j)
{
	if (l[i] < l[j] && l[j] < r[i] && r[i] < r[j])
		return 1;
	if (l[j] < l[i] && l[i] < r[j] && r[j] < r[i])
		return 1;
	return 0;
}

void bfs(int v)
{
	d[v] = 0, q.push(v);
	while (!q.empty()) {
		int u = q.front();
		q.pop();

		for (auto x: adj[u]) {
			if (d[x] == -1)
				d[x] = d[u] + 1, q.push(x);
			else if (d[x] == d[u]) {
				cout << 0;
				exit(0);
			}
		}
	}

	return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
	for (int i = 0; i < n; i++)
		cin >> l[i] >> r[i];

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (f(i, j))
				adj[i].push_back(j),
				adj[j].push_back(i);

	for (int i = 0; i < n; i++)
		d[i] = -1;

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (d[i] != -1)
			continue;

		bfs(i), ans++;
	}

	cout << p(2, ans);

    return 0;
}

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