QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#699988#6308. MagicIdtwteiML 0ms0kbC++141.2kb2024-11-02 11:29:352024-11-02 11:29:36

Judging History

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

  • [2024-11-02 11:29:36]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-11-02 11:29:35]
  • 提交

answer

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

const int N=5e3+5,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,s,t,l[N],r[N];
bitset<N*2> G[N*2];

bitset<N*2> dis; queue<int> q;
int bfs(){
	for(int i=1;i<=t;++i) dis[i]=0;
	while(!q.empty()) q.pop(); q.push(s),dis[s]=1;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v=G[u]._Find_first();v<=t;v=G[u]._Find_next(v)){
			if(!dis[v]){ 
				dis[v]=1,q.push(v);
				if(v==t) return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int df){
	if(u==t) return df;
	int res=df;
	for(int v=G[u]._Find_first(),k;res&&v<=t;v=G[u]._Find_next(v)){
		if(dis[v]){
			k=dinic(v,1);
			if(!k) dis[v]=0;
			else G[u][v]=0,G[v][u]=1,--res;
		}
	}
	return df-res;
}

int main(){

	n=rd,s=2*n+1,t=2*n+2;
	for(int i=1;i<=n;++i) G[s][l[i]=rd]=1,G[r[i]=rd][t]=1;
	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]) G[l[i]][r[j]]=1;
		
	int dflow=0,maxflow=0;
	while(bfs()) while(dflow=dinic(s,INF)) maxflow+=dflow;
	
	printf("%d\n", 2*n-maxflow);

	return 0;
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

5
2 3
6 7
1 9
5 10
4 8

output:


result: