Submission #411031

#	Time	Username	Problem	Language	Result	Execution time	Memory
411031		alishahali1382	Port Facility (JOI17_port_facility)	C++14	22 / 100	6053 ms	4044 KiB

port_facility

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=1000010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], B[MAXN];
int L[MAXN], R[MAXN];
int par[MAXN], parx[MAXN];

pii getpar(int x){
	if (par[x]==x) return {x, 0};
	pii p=getpar(par[x]);
	par[x]=p.first;
	parx[x]^=p.second;
	return {par[x], parx[x]};
}
int join(int x, int y){
//	debug2(x, y)
	pii xx=getpar(x);
	pii yy=getpar(y);
	if (xx.first!=yy.first){
		par[xx.first]=yy.first;
		parx[xx.first]=xx.second^yy.second^1;
		return 1;
	}
	if (xx.second^yy.second^1){
		cout<<"0\n";
		exit(0);
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>L[i]>>R[i];
		B[L[i]]=R[i];
		par[i]=i;
	}
	ans=n;
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++)
		if (L[i]<L[j] && L[j]<R[i] && R[i]<R[j]) ans-=join(i, j);
	
	ll res=1;
	while (ans--) res=res*2%mod;
	cout<<res<<"\n";
	
	return 0;
}

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