QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95620#6308. MagicwyzwyzML 0ms0kbC++14825b2023-04-10 21:44:412023-04-10 21:44:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-10 21:44:45]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-04-10 21:44:41]
  • 提交

answer

#include<cstdio>
#include<cctype>
#include<bitset>

#define maxn 5555

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f?-r:r;
}

int n,l[maxn],r[maxn],mat[maxn];

std::bitset<maxn> nvis,to[maxn];

bool dfs(int u){
	for(int i=(to[u]&nvis)._Find_first();i<=n;i=(to[u]&nvis)._Find_next(i)){
		nvis[i]=1;
		if(!mat[i]||dfs(mat[i]))
			return mat[i]=u,true;
	}
	return false;
}

int main(){
	n=read<int>();
	for(int i=1;i<=n;i++){
		l[i]=read<int>();
		r[i]=read<int>();
	}
	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])
				to[i][j]=1;
	int ans=2*n;
	for(int i=1;i<=n;i++)
		nvis.set(),ans-=dfs(i);
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

5
2 3
6 7
1 9
5 10
4 8

output:


result: