QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176934#6308. MagicdengziyueWA 1ms4400kbC++142.5kb2023-09-12 11:07:522023-09-12 11:07:52

Judging History

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

  • [2023-09-12 11:07:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4400kb
  • [2023-09-12 11:07:52]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define max_n 10000
#define s 0
#define t 165000
#define inf 0x3f3f3f3f
int n;
struct A{int l,r;}a[max_n+2];
int to[max_n+2];
int son[t+2][2];
int rt[max_n+2];
int ti=0;
struct E{int v,w,nx;}e[770002];
int ei=1;
int fir[t+max_n+2];
int de[t+max_n+2];
int q[t+max_n+2],ql,qr;
int ans=0;
void addedge(int u,int v,int w){
	e[++ei]=(E){v,w,fir[u]}; fir[u]=ei;
	e[++ei]=(E){u,0,fir[v]}; fir[v]=ei;
}
void build(int &o,int l,int r){
	if(!o)o=++ti;
	if(l>=r)return;
	int mid=(l+r)>>1;
	build(son[o][0],l,mid);
	build(son[o][1],mid+1,r);
	addedge(o,son[o][0],inf);
	addedge(o,son[o][1],inf);
}
void upd(int &o,int o2,int l,int r,int x,int w){
	o=++ti;
	if(l>=r){
		if(w)addedge(o,x+t,inf);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		son[o][1]=son[o2][1];
		upd(son[o][0],son[o2][0],l,mid,x,w);
	}
	else{
		son[o][0]=son[o2][0];
		upd(son[o][1],son[o2][1],mid+1,r,x,w);
	}
	addedge(o,son[o][0],inf);
	addedge(o,son[o][1],inf);
}
void query(int o,int l,int r,int ql,int qr,int w){
	if(!o)return;
	if(ql<=l&&r<=qr){addedge(w+t,o,inf); return;}
	int mid=(l+r)>>1;
	if(ql<=mid)query(son[o][0],l,mid,ql,qr,w);
	if(qr>mid)query(son[o][1],mid+1,r,ql,qr,w);
}
bool bfs(){
	memset(de,0,sizeof(de));
	de[s]=1; q[ql=qr=1]=s;
	while(ql<=qr){
		int u=q[ql++];
		for(int i=fir[u],v;i;i=e[i].nx){
			v=e[i].v;
			if(e[i].w&&!de[v]){de[v]=de[u]+1; q[++qr]=v;}
		}
	}
	return de[t];
}
int dfs(int u,int fl){
	if(u==t||!fl)return fl;
	int res=0;
	for(int i=fir[u],v,w;i;i=e[i].nx){
		v=e[i].v;
		if(e[i].w&&de[u]+1==de[v]){
			w=dfs(v,min(fl,e[i].w));
			if(w){
				e[i].w-=w; e[i^1].w+=w;
				fl-=w; res+=w;
			}
			else de[v]=0;
		}
	}
	if(!res)de[u]=0;
	return res;
}
int main(){
	#ifdef dzy
	freopen("QOJ6308_1.in","r",stdin);
//	freopen("QOJ6308_1.out","w",stdout);
	#endif
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d",&a[i].l,&a[i].r);
	memset(fir,0,sizeof(fir));
	memset(to,0,sizeof(to));
	for(int i=1;i<=n;++i){addedge(s,a[i].l+t,1); addedge(a[i].r+t,t,1);}
	for(int i=1;i<=n;++i)to[a[i].l]=a[i].r;
	build(rt[n*2+1],1,n*2);
	for(int i=n*2;i>=1;--i){
		if(to[i]){
			if(i+1<=to[i]-1)query(rt[i+1],1,n*2,i+1,to[i]-1,i);
			upd(rt[i],rt[i+1],1,n*2,to[i],0);
		}
		else upd(rt[i],rt[i+1],1,n*2,i,1);
	}
	printf("ti=%d ei=%d\n",ti,ei);
	while(bfs())ans+=dfs(s,inf);
	printf("%d\n",n*2-ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4400kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

ti=61 ei=211
9

result:

wrong output format Expected integer, but "ti=61" found