Submission #373271

#	Time	Username	Problem	Language	Result	Execution time	Memory
373271		8e7	Port Facility (JOI17_port_facility)	C++14	22 / 100	10 ms	4460 KiB

port_facility

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define maxn 2005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
pii a[maxn];
bool adj[maxn][maxn], found[maxn];
int col[maxn];
int poss = 1;
void dfs(int n, int c) {
	found[n] = 1;
	col[n] = c;
	for (int v = 0;v < maxn;v++) {
		if (!adj[n][v]) continue;
		if (!found[v]) {
			found[v] = 1;
			dfs(v, 3 - c);
		} else if (col[n] == col[v]) {
			poss = 0;
			return;
		}
	}
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) cin >> a[i].ff >> a[i].ss;
    sort(a, a + n);
    for (int i = 0;i < n;i++) {
    	for (int j = i + 1;j < n;j++) {
    		if (a[j].ff < a[i].ss && a[j].ss > a[i].ss) {
    			adj[i][j] = adj[j][i] = 1;
    		}
    	}
    }
    ll ans = 1;
    for (int i = 0;i < n;i++) {
    	if (!found[i]) {
    		ans = (ans * 2) % mod;
    		dfs(i, 1);
    	}
    }
    cout << (poss ? ans : 0) << "\n";
}

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