Submission #60039

#	Time	Username	Problem	Language	Result	Execution time	Memory
60039		FedericoS	Port Facility (JOI17_port_facility)	C++14	22 / 100	96 ms	16916 KiB

port_facility

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

int N;
int B[4005],A[4005];
vector<int> grafo[4005];
bool V[4005];
bool C[4005];
int cont;
bool flag=true;
int pot[4005];
int M=1000000007;

void DFS(int k){

	for(int f:grafo[k])
		if(V[f] and C[f]==C[k])
			flag=false;

	for(int f:grafo[k])
		if(!V[f])
		{
			V[f]=true;
			C[f]=!C[k];
			DFS(f);
		}

}

bool isNem(int x, int y){
	if(A[x]<A[y])
		swap(x,y);
	return !(B[x]<B[y] or A[x]>B[y]);
}

int main(){

	cin>>N;
	for(int i=0;i<N;i++)
		cin>>A[i]>>B[i];

	pot[0]=1;
	for(int i=1;i<N+2;i++)
		pot[i]=(2*pot[i-1])%M;

	for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++)
			if(isNem(i,j)){
				grafo[i].push_back(j);
				grafo[j].push_back(i);
			}

	for(int i=0;i<N;i++)
		if(!V[i]){
			V[i]=true;
			cont++;
			DFS(i);
		}

	if(flag)
		cout<<pot[cont];
	else
		cout<<0;

}

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