Submission #373091

#	Time	Username	Problem	Language	Result	Execution time	Memory
373091		Seanliu	Port Facility (JOI17_port_facility)	C++14	22 / 100	21 ms	3436 KiB

port_facility

#include <iostream>
#include <numeric>
#define int long long int
using namespace std;


const int maxN = 2e5 + 326, MOD = 1e9 + 7;
int N, A[maxN], B[maxN];

struct DSU{
	int dsu[maxN], sz[maxN];
	DSU(){}
	void init(int N){
		iota(dsu, dsu + N + 1, 0);
		fill(sz, sz + N + 1, 1);
	}
	void Flat(int x){
		if(x == dsu[x]) return;
		Flat(dsu[x]);
		sz[x] = sz[dsu[x]];
		dsu[x] = dsu[dsu[x]];
	}
	inline bool Merge(int a, int b){
		Flat(a);
		Flat(b);
		if(dsu[a] == dsu[b]) return false;
		sz[dsu[a]] += sz[dsu[b]];
		dsu[dsu[b]] = dsu[a];
		return true;
	}
} dsu;

bool intersect(int a, int b){
	if(A[a] > A[b]) swap(a, b);	
	return A[b] < B[a] && B[b] > B[a];
}

inline int mpow(int b, int e){
	int r = 1;
	for(int i = 0; i < 60; i++){
		if((e >> i) & 1) r = r * b % MOD;
		b = b * b % MOD;
	}
	return r;
}

signed main(){
	cin >> N;
	dsu.init(2 * N);
	if(N > 2000) return 0;
	for(int i = 0; i < N; i++){
		cin >> A[i] >> B[i];
		for(int j = 0; j < i; j++) if(intersect(i, j)){
			dsu.Merge(i, j + N) && dsu.Merge(i + N, j);
		}
	}
	int ans = 1;
	for(int i = 0; i < N; i++){
		dsu.Flat(i);
		dsu.Flat(i + N);
		if(dsu.dsu[i] == dsu.dsu[i + N]){
			cout << 0 << endl;
			return 0;
		}
		if(dsu.dsu[i] == i) ans++;
		if(dsu.dsu[i + N] == i + N) ans++;
	}
	cout << mpow(2, ans / 2) << endl;
}

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