제출 #533840

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

port_facility

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

bool flag, color[N], mark[N];
int a[N], b[N];
vector<int> G[N];

bool okay(int i, int j) {
	if(a[i] > a[j]) swap(i, j);
	return b[j] > b[i] && a[j] < b[i];
}

void dfs(int x) {
	mark[x] = 1;
	for(auto &i : G[x]) {
		if(mark[i]) {
			if(color[i] == color[x]) flag = 1;
			continue;
		}
		color[i] = color[x] - 1;
		dfs(i);
	}
}

ll poww(ll x, int y) {
	ll res = 1;
	for(; y; y /= 2, x = x * x % mod) {
		if(y & 1) {
			res = res * x % mod;
		}
	}
	return res;
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	for(int i = 1; i <= n; i++) {
		cin >>a[i] >>b[i];
	}

	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(okay(i, j)) {
				G[i].push_back(j), G[j].push_back(i);
			}
		}
	}

	int colorcnt = 0;
	for(int i = 1; i <= n; i++) if(!mark[i]) colorcnt++, dfs(i);
	
	if(flag) cout<<0;
	else cout<<poww(2, colorcnt);


    return 0;
}

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