Submission #953464

#	Time	Username	Problem	Language	Result	Execution time	Memory
953464		pcc	Port Facility (JOI17_port_facility)	C++17	10 / 100	9 ms	520 KiB

port_facility

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

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const ll mod = 1e9+7;
const int mxn = 2024;

ll pw(ll a,ll b){
	ll re = 1;
	while(b){
		if(b&1)re = re*a%mod;
		b>>=1;
		a = a*a%mod;
	}
	return re;
}
ll mad(ll a,ll b){
	a += b;
	return a>=mod?a-mod:a;
}

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){}
	void init(int n){
		for(int i = 0;i<=n;i++)dsu[i] = i,sz[i] = 1;
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
		return;
	}
};

pii arr[mxn];
int N;
int C = 0;
int col[mxn];
DSU cdsu,vdsu;
int op[mxn];
set<pii> st;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	cdsu.init(N*2+2);
	vdsu.init(N*2+2);
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc;
		op[arr[i].fs] = i;
		op[arr[i].sc] = -i;
	}
	for(int i = 1;i<=N;i++){
		for(int j = i+1;j<=N;j++){
			auto ta = arr[i],tb = arr[j];
			if(ta.fs>tb.fs)swap(ta,tb);
			if(ta.sc<tb.sc&&ta.sc>tb.fs){
				cdsu.onion(i*2,j*2-1);
				cdsu.onion(i*2-1,j*2);
			}
		}
	}
	int ans = 0;
	for(int i = 1;i<=N;i++){
		if(cdsu.root(i*2) == cdsu.root(i*2-1)){
			cout<<0;
			return 0;
		}
		if(cdsu.root(i*2) == i*2)ans++;
		if(cdsu.root(i*2-1) == i*2-1)ans++;
	}
	assert(ans&&ans%2==0);
	cout<<pw(2,ans>>1);
}

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