제출 #426924

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

port_facility

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
#define l first
#define r second
typedef long long lint;
typedef pair<lint,lint> ii;

const lint mod = 1000000007;

int p[2000005];
int ans;

int findSet(int u){
	if(p[u] == u) return u;
	else return p[u] = findSet(p[u]);
}

bool unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return false;
	if(rand()&1) swap(u,v);
	p[u] = v;
	return true;
}

void merge(int a, int b){
	if(unionSet(a*2, b*2+1)) ans--;
	unionSet(a*2+1, b*2);
}

ii arr[4005];

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	ans = n;
	for(int i = 0;i < n;i++) cin >> arr[i].l >> arr[i].r;
	for(int i = 0;i < 2*n;i++) p[i] = i;
	
	for(int i = 0;i < n;i++){
		for(int j = i+1;j < n;j++){
			ii a = arr[i], b = arr[j];
			if(a.l > b.l) swap(a,b);
			
			if(a.l < b.l and b.l < a.r and a.r < b.r){
				//show2(i,j);
				merge(i,j);
			}
		}
	}
	
	for(int i = 0;i < n;i++){
		if(findSet(i*2) == findSet(i*2+1)){
			cout << 0;
			return 0;
		}
	}
	
	lint actlans = 1;
	for(int i = 0;i < ans;i++){
		actlans *= 2;
		if(actlans >= mod) actlans -= mod;
	}
	
	cout << actlans;
}

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