제출 #982594

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

port_facility

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		X						real()
#define		Y						imag()
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

int n;
const int maxn = 4000 + 4;
const int mod = 1e9 + 7;
pii A[maxn]; int ind[maxn];
pii p[maxn]; int num;

pii get(int a) {
	if (p[a].F == a) return p[a];
	auto x = get(p[a].F); x.S ^= p[a].S;
	return (p[a] = x);
}

void merge(int u, int v) {
	pii a = get(u), b = get(v);
	if (a.F == b.F) {
		if (a.S == b.S) kill(0);
		return ;
	}
	p[a.F] = Mp(b.F, (a.S == b.S)); num--;
}

ll power(ll a, ll b) {
	if (b == 0) return 1;
	return power(a * a % mod, b / 2) * ((b & 1) ? a : 1) % mod;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i].F >> A[i].S;
		A[i].F--; A[i].S--;
		ind[A[i].F] = i; ind[A[i].S] = i;
	}
	
	num = n;
	for (int i = 0; i < n; i++) p[i] = Mp(i, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (A[j].F > A[i].F && A[j].F < A[i].S && A[j].S > A[i].S) {
				merge(i, j);
			}
		}
	}
	
	cout << power(2, num) << endl;
	
	return 0;
}

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