Submission #427812

#	Time	Username	Problem	Language	Result	Execution time	Memory
427812		errorgorn	Port Facility (JOI17_port_facility)	C++17	22 / 100	84 ms	17956 KiB

port_facility

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

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD=1000000007;

int n;
ii arr[1000005];

vector<int> al[2005];
bool black[2005];
bool vis[2005];

int ans=1;

void dfs(int i){
	vis[i]=true;
	
	for (auto &it:al[i]){
		if (!vis[it]){
			black[it]=!black[i];
			dfs(it);
		}
		else if (black[it]==black[i]){
			ans=0;
		}
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;

	rep(x,0,n) rep(y,0,n){
		if (arr[x].fi<arr[y].fi && arr[y].fi<arr[x].se && arr[x].se<arr[y].se){
			al[x].pub(y);
			al[y].pub(x);
			
			//cout<<x<<" "<<y<<endl;
		}
	}
	
	rep(x,0,n) if (!vis[x]){
		dfs(x);
		ans=ans*2%MOD;
	}
	
	cout<<ans<<endl;
}

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