QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410153#6615. Cross the MazeSiilhouetteWA 13ms9180kbC++233.9kb2024-05-13 16:42:042024-05-13 16:42:04

Judging History

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

  • [2024-05-13 16:42:04]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:9180kb
  • [2024-05-13 16:42:04]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<set>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;

const int N=200010;
const int M=200010;
const int inf=1000000000;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
int n,m,q,st,ed,tot=1,head[N],d[N],cur[N];
vector<pair<int,int> >stx,edx;
vector<int>c[110];
struct Edge{
	int ver,suiv,edge;
	char dir;
}e[M<<1];

inline void _lnk(int x,int y,int z,char ch)
{
	e[++tot].ver=y;
	e[tot].edge=z;
	e[tot].suiv=head[x];
	head[x]=tot;
	e[tot].dir=ch;
}

inline void lnk(int x,int y,int z,char ch)
{
	_lnk(x,y,z,ch),_lnk(y,x,0,ch);
}

inline int dfs(int x,int flow)
{
	if(x==ed)return flow;
	int minflow,resflow=0;
	for(int &i=cur[x];i;i=e[i].suiv)
	//for(int i=head[x];i;i=e[i].suiv)
	{
		int y=e[i].ver;
		if(d[y]!=d[x]+1||!e[i].edge)continue;
		minflow=dfs(y,min(flow,e[i].edge));
		flow-=minflow;
		e[i].edge-=minflow;
		resflow+=minflow;
		e[i^1].edge+=minflow;
		if(!flow)break;
	}
	if(!resflow)d[x]=-1;
	return resflow;
}


inline bool bfs()
{
	memset(d,-1,sizeof(d));
	queue<int>q;
	q.push(st);
	d[st]=0;
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].suiv)
		{
			int y=e[i].ver;
			if(~d[y]||!e[i].edge)continue;
			d[y]=d[x]+1;
			q.push(y);
		}
	}
	return ~d[ed];
}


inline ll dinic()
{
	ll res=0;
	while(bfs())
	{
		memcpy(cur,head,sizeof(head));
		res+=1ll*dfs(st,inf);
	}
	return res;
}

inline int _(int dep,int op,int x,int y)
{
	return ((dep-1)*2+op)*n*m+(x-1)*n+y;
}

inline void dfs1(int x,int id)
{
	//cout<<"dfs1 "<<x<<" "<<id<<endl;
	if(x==ed)return;
	for(int i=head[x];i;i=e[i].suiv)
	{
		int y=e[i].ver,z=e[i].edge;
		if((i&1)||z)continue;
		if(e[i].dir!=0)c[id].push_back(e[i].dir)
			//,cout<<"id "<<id<<" "<<char(e[i].dir)<<endl
			;
		dfs1(y,id);
	}
}

inline bool valid(int mid)
{
	
	tot=1;
	memset(head,0,sizeof(head));
	st=0,ed=N-1;
	for(auto pos:stx)
		lnk(st,_(1,0,pos.first,pos.second),1,0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			lnk(_(1,0,i,j),_(1,1,i,j),1,0);
	for(int i=1;i<=q;i++)
		lnk(N-1-i,ed,1,0);
	for(int i=1;i<=q;i++)
		lnk(_(1,1,edx[i-1].first,edx[i-1].second),N-1-i,1,0);
	int ans=0;
	for(int i=1;i<=mid;i++)
	{
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
			{
				for(int l=0;l<4;l++)
				{
					int posx=j+dx[l],posy=k+dy[l];
					if(posx<1||posx>n||posy<1||posy>m)continue;
					char ch;
					if(dx[l]==0&&dy[l]==1)ch='R';
					else if(dx[l]==0&&dy[l]==-1)ch='L';
					else if(dx[l]==-1&&dy[l]==0)ch='U';
					else ch='D';
					//cout<<"lnk "<<ch<<endl;
					lnk(_(i,1,j,k),_(i+1,0,posx,posy),1,ch);
				}
				lnk(_(i+1,0,j,k),_(i+1,1,j,k),1,0);
			}
		for(int j=1;j<=q;j++)
			lnk(_(i+1,1,edx[j-1].first,edx[j-1].second),N-1-j,1,0);
	}
	return dinic()>=q;
}


signed main()
{
	scanf("%d%d%d",&q,&n,&m);
	for(int i=1,x,y;i<=q;i++)
		scanf("%d%d",&x,&y),stx.push_back(make_pair(x,y));
	for(int i=1,x,y;i<=q;i++)
		scanf("%d%d",&x,&y),edx.push_back(make_pair(x,y));
	
	//dinic();
	//cout<<maxflow<<endl;
	//ans=3;
	//cout<<valid(1)<<endl;
	int l=1,r=n*m,ans=-1;
	while(l<=r)
	{
		int mid=l+r>>1;
		//cout<<"valid "<<mid<<endl;
		if(valid(mid))r=mid-1,ans=mid
			//,cout<<"ok"<<endl
			;
		else l=mid+1
			//,cout<<"no"<<endl
			;
	}
	valid(ans);
	printf("%d\n",ans);
	for(int i=1;i<=q;i++)
		dfs1(_(1,0,stx[i-1].first,stx[i-1].second),i);
	for(int i=1;i<=q;i++)
	{
		printf("%d %d ",stx[i-1].first,stx[i-1].second);
		int posx=stx[i-1].first,posy=stx[i-1].second;
		for(int j=1,lim=c[i].size();j<=lim;j++)
		{
			if(c[i][j-1]=='R')posy+=1;
			if(c[i][j-1]=='L')posy-=1;
			if(c[i][j-1]=='U')posx-=1;
			if(c[i][j-1]=='D')posx+=1;
		}
		printf("%d %d ",posx,posy);
		for(int j=1,lim=c[i].size();j<=ans;j++)
			printf("%c",j<=lim?c[i][j-1]:'P');
		putchar('\n');
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 6256kb

input:

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

output:

2
1 1 1 3 RR
1 4 2 3 LD
4 4 2 4 UU

result:

ok answer 2

Test #2:

score: 0
Accepted
time: 2ms
memory: 6128kb

input:

3 2 2
1 1
1 2
2 2
1 1
2 1
2 2

output:

1
1 1 2 1 D
1 2 1 1 L
2 2 2 2 P

result:

ok answer 1

Test #3:

score: 0
Accepted
time: 0ms
memory: 6184kb

input:

2 3 3
1 1
1 3
1 2
2 2

output:

2
1 1 2 2 DR
1 3 1 2 LP

result:

ok answer 2

Test #4:

score: 0
Accepted
time: 2ms
memory: 6900kb

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 DRDDDDDDDP
3 8 10 5 LLLDDDDDDD

result:

ok answer 10

Test #5:

score: 0
Accepted
time: 3ms
memory: 6908kb

input:

6 10 10
4 9
4 2
3 6
10 1
10 10
4 1
6 8
5 10
6 3
5 1
2 9
3 2

output:

5
4 9 6 8 RDLLD
4 2 3 2 UPPPP
3 6 2 9 RRRUP
10 1 5 1 UUUUU
10 10 5 10 UUUUU
4 1 6 3 DRRDP

result:

ok answer 5

Test #6:

score: 0
Accepted
time: 4ms
memory: 7204kb

input:

8 10 10
5 1
6 8
6 3
6 4
3 10
9 5
6 7
4 1
3 8
7 3
1 2
8 6
5 8
7 6
9 4
4 1

output:

4
5 1 4 1 UPPP
6 8 5 8 UPPP
6 3 7 3 DPPP
6 4 8 6 RRDD
3 10 3 8 LLPP
9 5 9 4 LPPP
6 7 7 6 LDPP
4 1 1 2 RUUU

result:

ok answer 4

Test #7:

score: 0
Accepted
time: 3ms
memory: 6852kb

input:

1 10 10
8 3
8 4

output:

1
8 3 8 4 R

result:

ok answer 1

Test #8:

score: 0
Accepted
time: 0ms
memory: 6888kb

input:

1 10 10
10 1
6 6

output:

9
10 1 6 6 RRRRRUUUU

result:

ok answer 9

Test #9:

score: 0
Accepted
time: 12ms
memory: 7208kb

input:

8 10 10
7 8
4 6
10 9
4 7
4 3
10 6
3 3
2 7
3 7
2 10
3 8
1 9
6 1
3 10
10 2
6 4

output:

7
7 8 2 10 RRUUUUU
4 6 3 10 RRRRUPP
10 9 10 2 LLLLLLL
4 7 3 8 RUPPPPP
4 3 3 7 RDRRRUU
10 6 6 4 LLUUUUP
3 3 6 1 LLDDDPP
2 7 1 9 DURRUPP

result:

ok answer 7

Test #10:

score: 0
Accepted
time: 0ms
memory: 7188kb

input:

1 10 10
10 3
2 6

output:

11
10 3 2 6 RRRUUUUUUUU

result:

ok answer 11

Test #11:

score: 0
Accepted
time: 0ms
memory: 9180kb

input:

3 10 10
7 8
4 4
3 1
7 10
6 7
2 4

output:

5
7 8 7 10 RRPPP
4 4 6 7 RRRDD
3 1 2 4 RRRUP

result:

ok answer 5

Test #12:

score: 0
Accepted
time: 9ms
memory: 6916kb

input:

9 10 10
6 4
1 7
2 1
5 6
10 8
3 5
9 9
9 2
4 9
5 3
3 2
6 9
2 2
9 4
7 8
2 8
1 1
4 8

output:

5
6 4 3 2 LULUU
1 7 2 8 RDPPP
2 1 1 1 RLUPP
5 6 5 3 LLLPP
10 8 7 8 UUUPP
3 5 2 2 LLLUP
9 9 6 9 UUUPP
9 2 9 4 RRPPP
4 9 4 8 LPPPP

result:

ok answer 5

Test #13:

score: 0
Accepted
time: 4ms
memory: 8788kb

input:

2 10 10
9 8
3 3
5 8
4 9

output:

7
9 8 5 8 UUUUPPP
3 3 4 9 RRRRRRD

result:

ok answer 7

Test #14:

score: 0
Accepted
time: 2ms
memory: 6868kb

input:

8 10 10
10 5
8 4
2 8
2 4
10 8
6 6
1 7
10 1
8 6
10 5
10 2
5 9
8 10
10 4
3 9
4 2

output:

4
10 5 10 5 PPPP
8 4 10 4 DDPP
2 8 5 9 RDDD
2 4 4 2 LLDD
10 8 8 10 RRUU
6 6 8 6 DDPP
1 7 3 9 RRDD
10 1 10 2 RPPP

result:

ok answer 4

Test #15:

score: 0
Accepted
time: 0ms
memory: 6896kb

input:

1 10 10
1 9
2 10

output:

2
1 9 2 10 RD

result:

ok answer 2

Test #16:

score: 0
Accepted
time: 6ms
memory: 8312kb

input:

8 10 10
5 10
3 8
2 8
3 5
4 2
8 2
7 9
3 4
8 9
9 6
3 6
10 2
4 10
10 6
6 5
5 5

output:

6
5 10 4 10 UPPPPP
3 8 8 9 RDDDDD
2 8 3 6 LLDPPP
3 5 6 5 RLDDDP
4 2 10 2 DDDDDD
8 2 10 6 DDRRRR
7 9 9 6 DLLLDP
3 4 5 5 RDDPPP

result:

ok answer 6

Test #17:

score: 0
Accepted
time: 3ms
memory: 7200kb

input:

1 10 10
8 6
1 8

output:

9
8 6 1 8 RRUUUUUUU

result:

ok answer 9

Test #18:

score: 0
Accepted
time: 8ms
memory: 6920kb

input:

10 10 10
7 10
4 4
9 10
5 7
10 7
4 1
1 5
6 7
6 4
5 3
5 7
1 9
1 6
8 3
5 1
10 8
2 6
4 2
3 10
3 1

output:

5
7 10 3 10 UUUUP
4 4 3 1 LLLUP
9 10 10 8 LLDPP
5 7 1 6 LUUUU
10 7 5 7 UUUUU
4 1 4 2 RPPPP
1 5 1 9 RRRRP
6 7 2 6 ULUUU
6 4 8 3 LDDPP
5 3 5 1 LLPPP

result:

ok answer 5

Test #19:

score: 0
Accepted
time: 7ms
memory: 8892kb

input:

7 10 10
4 5
1 5
6 5
9 6
5 5
9 3
1 10
10 6
6 2
5 1
2 7
8 1
7 10
6 3

output:

6
4 5 6 2 LLLDDP
1 5 2 7 RRDPPP
6 5 6 3 LLPPPP
9 6 10 6 DPPPPP
5 5 5 1 LLLLPP
9 3 8 1 LLUPPP
1 10 7 10 DDDDDD

result:

ok answer 6

Test #20:

score: 0
Accepted
time: 3ms
memory: 6852kb

input:

6 10 10
9 7
4 1
9 1
7 9
2 6
9 5
5 1
4 1
2 10
4 10
3 1
1 7

output:

8
9 7 4 10 RRRUUUUU
4 1 4 1 PPPPPPPP
9 1 3 1 UUUUUUPP
7 9 2 10 RUUUUUPP
2 6 1 7 RUPPPPPP
9 5 5 1 LLLLUUUU

result:

ok answer 8

Test #21:

score: 0
Accepted
time: 9ms
memory: 9056kb

input:

10 10 10
7 7
8 6
10 3
6 2
10 8
1 10
9 5
1 2
8 3
10 9
8 9
8 10
6 4
7 8
4 3
3 5
3 9
6 1
8 7
10 2

output:

5
7 7 7 8 RPPPP
8 6 8 7 RPPPP
10 3 10 2 LPPPP
6 2 6 1 LPPPP
10 8 8 10 RRUUP
1 10 3 9 LDDPP
9 5 6 4 LUUUP
1 2 3 5 RDDRR
8 3 4 3 UUUUP
10 9 8 9 UUPPP

result:

ok answer 5

Test #22:

score: 0
Accepted
time: 11ms
memory: 6916kb

input:

10 10 10
2 9
1 2
3 9
6 9
3 3
9 2
2 4
5 8
1 6
4 9
1 10
6 10
3 6
2 5
4 2
7 3
10 2
9 1
2 9
5 8

output:

8
2 9 2 9 PPPPPPPP
1 2 7 3 RDDDDDDP
3 9 1 10 RUUPPPPP
6 9 6 10 RPPPPPPP
3 3 10 2 LDDDDDDD
9 2 9 1 LPPPPPPP
2 4 2 5 RPPPPPPP
5 8 5 8 PPPPPPPP
1 6 3 6 DDPPPPPP
4 9 4 2 LLLLLLLP

result:

ok answer 8

Test #23:

score: 0
Accepted
time: 10ms
memory: 6864kb

input:

10 10 10
10 6
9 2
7 7
7 3
6 8
5 4
2 10
1 1
5 9
4 6
5 1
9 9
9 1
7 6
3 2
4 8
7 7
9 7
3 1
6 10

output:

4
10 6 9 7 RUPP
9 2 9 1 LPPP
7 7 7 7 PPPP
7 3 5 1 LLUU
6 8 7 6 LLDP
5 4 3 2 LLUU
2 10 6 10 DDDD
1 1 3 1 DDPP
5 9 9 9 DDDD
4 6 4 8 RRPP

result:

ok answer 4

Test #24:

score: 0
Accepted
time: 7ms
memory: 6668kb

input:

10 1 100
1 17
1 49
1 12
1 37
1 83
1 44
1 75
1 78
1 72
1 3
1 75
1 47
1 55
1 81
1 6
1 59
1 17
1 68
1 28
1 24

output:

13
1 17 1 17 PPPPPPPPPPPPP
1 49 1 47 LLPPPPPPPPPPP
1 12 1 24 RRRRRRRRRRRRP
1 37 1 28 LLLLLLLLLPPPP
1 83 1 81 LLPPPPPPPPPPP
1 44 1 55 RRRRRRRRRRRPP
1 75 1 75 PPPPPPPPPPPPP
1 78 1 68 LLLLLLLLLLPPP
1 72 1 59 LLLLLLLLLLLLL
1 3 1 6 RRRPPPPPPPPPP

result:

ok answer 13

Test #25:

score: 0
Accepted
time: 10ms
memory: 6656kb

input:

10 1 100
1 43
1 75
1 59
1 42
1 26
1 33
1 88
1 7
1 24
1 95
1 68
1 31
1 39
1 74
1 66
1 67
1 28
1 70
1 86
1 58

output:

25
1 43 1 66 RRRRRRRRRRRRRRRRRRRRRRRPP
1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP
1 59 1 68 LRRRRRRRRRRPPPPPPPPPPPPPP
1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR
1 26 1 28 RRPPPPPPPPPPPPPPPPPPPPPPP
1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR
1 88 1 86 LLPPPPPPPPPPPPPPPPPPPPPPP
1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRP
1 24 1 39 ...

result:

ok answer 25

Test #26:

score: 0
Accepted
time: 13ms
memory: 6960kb

input:

10 1 100
1 88
1 38
1 43
1 99
1 63
1 24
1 44
1 31
1 47
1 52
1 6
1 14
1 55
1 15
1 82
1 57
1 73
1 74
1 97
1 51

output:

23
1 88 1 82 LLLLLLPPPPPPPPPPPPPPPPP
1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL
1 43 1 51 RRRRRRRRPPPPPPPPPPPPPPP
1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP
1 63 1 73 LLLLLLRRRRRRRRRRRRRRRRP
1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP
1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP
1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP
1 47 1 55 RRRRRRRRPPPPPPPP...

result:

ok answer 23

Test #27:

score: -100
Wrong Answer
time: 3ms
memory: 6724kb

input:

10 100 1
6 1
96 1
41 1
76 1
97 1
72 1
94 1
82 1
23 1
40 1
31 1
33 1
84 1
77 1
41 1
24 1
39 1
68 1
8 1
82 1

output:

17
6 1 7 1 DPPPPPPPPPPPPPPPP
96 1 96 1 PPPPPPPPPPPPPPPPP
41 1 41 1 PPPPPPPPPPPPPPPPP
76 1 76 1 PPPPPPPPPPPPPPPPP
97 1 97 1 PPPPPPPPPPPPPPPPP
72 1 72 1 PPPPPPPPPPPPPPPPP
94 1 94 1 PPPPPPPPPPPPPPPPP
82 1 82 1 PPPPPPPPPPPPPPPPP
23 1 24 1 DPPPPPPPPPPPPPPPP
40 1 40 1 PPPPPPPPPPPPPPPPP

result:

wrong answer ropes not match