Submission #373271

#TimeUsernameProblemLanguageResultExecution timeMemory
3732718e7Port Facility (JOI17_port_facility)C++14
22 / 100
10 ms4460 KiB
//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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...