Submission #559488

#	Time	Username	Problem	Language	Result	Execution time	Memory
559488		amunduzbaev	Port Facility (JOI17_port_facility)	C++17	22 / 100	42 ms	32744 KiB

port_facility

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

//~ struct ST{
	
//~ };

const int N = 2e3 + 5;
const int mod = 1e9 + 7;
vector<int> edges[N];
int l[N], r[N], id[N], used[N];
int c[N];

void dfs(int u){
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x]){
			if(c[x] == c[u]){
				cout<<0<<"\n";
				exit(0);
			} 
		} else {
			c[x] = c[u] ^ 1;
			dfs(x);
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; 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((l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) || (l[j] < l[i] && r[j] < r[i] && l[i] < r[j])){
				edges[i].push_back(j);
				edges[j].push_back(i);
			}
		}
	}
	
	int c = 0;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		dfs(i); c++;
	}
	
	int res = 1;
	while(c--){
		res = res * 2ll % mod;
	}
	
	cout<<res<<"\n";
}

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