QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#393710#6615. Cross the Mazetz3528WA 1ms3840kbC++203.2kb2024-04-19 09:24:462024-04-19 09:24:46

Judging History

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

  • [2024-04-19 09:24:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-04-19 09:24:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int p_max=110,q_max=1000100;
int n,a,b,s,t,edge=1,l=0,r=200;
int d[q_max],now[q_max],to[q_max],Next[q_max],fir[q_max];
int v[q_max],ans=0;
int x[p_max][2],y[p_max][2],h[p_max];
void add(int x,int y,int w){
	to[++edge]=y; v[edge]=w; Next[edge]=fir[x]; fir[x]=edge;
	to[++edge]=x; v[edge]=0; Next[edge]=fir[y]; fir[y]=edge;
}
bool bfs(){
	for(int i=1;i<=t;i++) d[i]=0;
	queue<int> q;
	q.push(s);
	d[s]=1;
	now[s]=fir[s];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=Next[i]){
			if(!d[to[i]]&&v[i]){//为分层且有权值的边才进行遍历
				q.push(to[i]);
				now[to[i]]=fir[to[i]];
				d[to[i]]=d[x]+1;
				if(to[i]==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u,int flow){
	if(u==t) return flow;
	int rest=flow,k,i;
	for(i=now[u];i&&rest;i=Next[i]){
		if(v[i]&&d[to[i]]==d[u]+1){
			k=dfs(to[i],min(rest,v[i]));//找最小流
			if(!k) d[to[i]]=0;//剪枝,删掉已经增广过的点
			v[i]-=k;
			v[i^1]+=k;
			rest-=k;//从u出发的点要消耗k
		}
	}
	now[u]=i;//将u的下一个结点置空,避免重复
	return flow-rest;//返回在u点的最大流出
}
int dinic(){
	ans=0;
	while(bfs()) ans+=dfs(s,1e9);
	return ans;
}
int num(int k,int x,int y,int flag){return k*a*b+(x-1)*b+y+flag*(a+b+1)*a*b;}
bool check(int mid){
	for(int i=0;i<=t;i++) fir[i]=0;
	edge=1;
	for(int i=1;i<=n;i++) add(s,num(0,x[i][0],y[i][0],0),1);
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			for(int k=0;k<mid;k++){
				add(num(k,i,j,0),num(k,i,j,1),1);
				add(num(k,i,j,1),num(k+1,i,j,0),1);
				if(i>1) add(num(k,i,j,1),num(k+1,i-1,j,0),1);
				if(j>1) add(num(k,i,j,1),num(k+1,i,j-1,0),1);
				if(i<a) add(num(k,i,j,1),num(k+1,i+1,j,0),1);
				if(j<b) add(num(k,i,j,1),num(k+1,i,j+1,0),1);
			}
			add(num(mid,i,j,0),num(mid,i,j,1),1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=mid;j++){
			add(num(j,x[i][1],y[i][1],1),num(mid,a,b,1)+i,1);
		}
		add(num(mid,a,b,1)+i,t,1);
	}
	return dinic()==n;
}
vector<char> c;
void dfs1(int x,int y,int k,int flag){
//	cout<<x<<' '<<y<<endl;
	int u=num(k,x,y,flag);
	if(u>num(a+b,a,b,1)) return ;
	for(int i=fir[u];i;i=Next[i]){
		if(v[i]) continue;
		if(to[i]==num(k,x,y,1)) dfs1(x,y,k,1);
		if(to[i]==num(k+1,x+1,y,0)) {c.push_back('D');dfs1(x+1,y,k+1,0);}
		if(to[i]==num(k+1,x,y+1,0)) {c.push_back('R');dfs1(x,y+1,k+1,0);}
		if(to[i]==num(k+1,x-1,y,0)) {c.push_back('U');dfs1(x-1,y,k+1,0);}
		if(to[i]==num(k+1,x,y-1,0)) {c.push_back('L');dfs1(x,y-1,k+1,0);}
	}
}
int main(){
	cin>>n>>a>>b;
	s=0;t=num(a+b,a,b,1)+n+1;
	for(int i=1;i<=n;i++) cin>>x[i][0]>>y[i][0];
	for(int i=1;i<=n;i++) cin>>x[i][1]>>y[i][1];
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	cout<<l<<endl;
	int u=num(0,x[1][0],y[1][0],0);
	for(int i=1;i<=n;i++){
		int j=0;
		c.clear();
		dfs1(x[i][0],y[i][0],0,0);
		cout<<x[i][0]<<' '<<y[i][0]<<' ';
		for(auto it:c){
			if(it=='U') x[i][0]--;
			if(it=='D') x[i][0]++;
			if(it=='L') y[i][0]--;
			if(it=='R') y[i][0]++;
		}
		cout<<x[i][0]<<' '<<y[i][0]<<' ';
		for(auto it:c) cout<<it,j++;
		while(j<l) cout<<'P',j++;
		cout<<endl;
	}
	return 0;
}

详细

Test #1:

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

input:

3 4 4
1 1
1 4
4 4
1 3
2 3
2 4

output:

2
1 1 1 1 PP
1 4 2 4 DP
4 4 4 4 PP

result:

wrong answer ropes not match