QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218962#2924. Lone Rookucup-team1004WA 68ms46560kbC++144.0kb2023-10-18 21:11:092023-10-18 21:11:09

Judging History

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

  • [2023-10-18 21:11:09]
  • 评测
  • 测评结果:WA
  • 用时:68ms
  • 内存:46560kb
  • [2023-10-18 21:11:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=755,V=N*N;
int n,m,sx,sy,tx,ty;
char a[N][N];
struct Map{
	set<int>h[N],l[N];
	void insert(int x,int y){
		h[x].insert(y),l[y].insert(x);
	}
	void erase(int x,int y){
		h[x].erase(y),l[y].erase(x);
	}
	pair<int,int> getH(int x,int y){
		int pre=0,nex=m+1;
		auto it=h[x].lower_bound(y);
		if(it!=h[x].begin())pre=*prev(it);
		it=h[x].upper_bound(y);
		if(it!=h[x].end())nex=*it;
		return {pre,nex};
	}
	pair<int,int> getL(int x,int y){
		int pre=0,nex=n+1;
		auto it=l[y].lower_bound(x);
		if(it!=l[y].begin())pre=*prev(it);
		it=l[y].upper_bound(x);
		if(it!=l[y].end())nex=*it;
		return {pre,nex};
	}
}ok,ban;
const int dx[8]={2,2,1,1,-2,-2,-1,-1};
const int dy[8]={1,-1,2,-2,1,-1,2,-2};
int k,cnt[N][N],id[N][N],fa[V];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
vector<pair<int,int> >p[V];
bool merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return 0;
	if(p[x].size()>p[y].size())p[x].swap(p[y]);
	for(auto pt:p[x])p[y].push_back(pt);
	return p[x].clear(),fa[x]=y,1;
}
bool valid(int x,int y){
	return 1<=x&&x<=n&&1<=y&&y<=m;
}
void reach(int x,int y){
	// debug("reach",x,y,k);
	int lx,rx,ly,ry,Lx,Rx,Ly,Ry;
	tie(ly,ry)=ok.getH(x,y),tie(lx,rx)=ok.getL(x,y);
	tie(Ly,Ry)=ban.getH(x,y),tie(Lx,Rx)=ban.getL(x,y);
	// debug("reach",x,y,ly,Ly);
	if(valid(x,ly)&&ly>Ly)merge(id[x][ly],id[x][y]);
	if(valid(x,ry)&&ry<Ry)merge(id[x][ry],id[x][y]);
	if(valid(lx,y)&&lx>Lx)merge(id[lx][y],id[x][y]);
	if(valid(rx,y)&&rx<Rx)merge(id[rx][y],id[x][y]);
	if(find(id[x][y])==find(id[sx][sy])){
		// if(x==8&&y==3)debug("ok");
		if(valid(x,Ly)&&!cnt[x][Ly])merge(id[x][Ly],id[x][y]);
		if(valid(x,Ry)&&!cnt[x][Ry])merge(id[x][Ry],id[x][y]);
		if(valid(Lx,y)&&!cnt[Lx][y])merge(id[Lx][y],id[x][y]);
		if(valid(Rx,y)&&!cnt[Rx][y])merge(id[Rx][y],id[x][y]);
	}
	ok.insert(x,y);
}
queue<pair<int,int> >q;
void reduce(){
	for(auto pt:p[find(id[sx][sy])]){
		ban.erase(pt.first,pt.second);
		q.push(pt);
	}
	p[find(id[sx][sy])].clear();
}
void topo(){
	for(int i,j;!q.empty();){
		tie(i,j)=q.front(),q.pop();
		reach(i,j),reduce();
		for(int k=0;k<8;k++){
			int x=i+dx[k],y=j+dy[k];
			if(!valid(x,y))continue;
			if(!--cnt[x][y]){
				if(a[x][y]=='K'){
					p[find(id[x][y])].push_back({x,y});
				}
				reach(x,y);
				reduce();
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			id[i][j]=++k,fa[k]=k;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='R')sx=i,sy=j,a[i][j]='.';
			else if(a[i][j]=='T')tx=i,ty=j,a[i][j]='.';
			else if(a[i][j]=='K'){
				ban.insert(i,j);
				for(int k=0;k<8;k++){
					int x=i+dx[k],y=j+dy[k];
					if(valid(x,y))cnt[x][y]++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!cnt[i][j]){
				if(a[i][j]=='K'){
					p[find(id[i][j])].push_back({i,j});
				}
				reach(i,j);
				reduce();
				// if(find(1)==find(3)){
				// 	// debug(i,j);
				// 	for(int i=1;i<=n;i++){
				// 		vector<int>col;
				// 		for(int j=1;j<=m;j++){
				// 			col.push_back(find(id[i][j]));
				// 		}
				// 		// debug("col",i,col);
				// 	}
				// }
			}
		}
	}
	topo();
	// for(int i=1;i<=n;i++){
	// 	vector<int>col;
	// 	for(int j=1;j<=m;j++){
	// 		// col.push_back(find(id[i][j]));
	// 		col.push_back(find(id[i][j])==find(id[sx][sy]));
	// 	}
	// 	debug("col",col);
	// }
	puts(find(id[sx][sy])==find(id[tx][ty])?"yes":"no");
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 19508kb

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

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

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 5ms
memory: 24008kb

input:

5 3
KKT
.K.
K..
...
KKR

output:

yes

result:

ok single line: 'yes'

Test #4:

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

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

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

input:

2 5
RKKK.
...KT

output:

no

result:

ok single line: 'no'

Test #6:

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

input:

5 6
.....T
..K...
..KK..
...K..
R.....

output:

no

result:

ok single line: 'no'

Test #7:

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

input:

3 4
...K
T.KR
..K.

output:

no

result:

ok single line: 'no'

Test #8:

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

input:

6 3
.R.
...
...
KKK
.K.
.T.

output:

yes

result:

ok single line: 'yes'

Test #9:

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

input:

6 6
..K..T
..K...
......
..KK.K
...K..
R.....

output:

no

result:

ok single line: 'no'

Test #10:

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

input:

6 6
..K...
..KTK.
......
..KK..
...K..
R.....

output:

yes

result:

ok single line: 'yes'

Test #11:

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

input:

14 6
T.K..K
......
K....K
KKK.KK
KKK.KK
......
......
..K.KK
.K...K
......
..KK.K
...K..
......
R.K.K.

output:

yes

result:

ok single line: 'yes'

Test #12:

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

input:

9 12
R...K.....KK
...KKK.T..KK
...K......KK
...K......KK
.....K....KK
..........KK
KK.......KKK
.KK...K..KKK
..K......KKK

output:

yes

result:

ok single line: 'yes'

Test #13:

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

input:

17 14
......KK......
......KK......
RKK...KK......
K.....KKKK...K
......KKKK..KK
......KKKK..KK
...KKKKK.....K
..K.KKKKK.....
............K.
............K.
....K.........
...........KK.
KKKKKKKKKK.KK.
KK..KKKKK.....
T.............
...K.......K..
.........KKKKK

output:

yes

result:

ok single line: 'yes'

Test #14:

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

input:

10 10
.K.K.K.K.T
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
K.K.K.K.K.
.K.K.K.K.K
R.K.K.K.K.

output:

no

result:

ok single line: 'no'

Test #15:

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

input:

4 3
K.T
...
.K.
R..

output:

no

result:

ok single line: 'no'

Test #16:

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

input:

4 3
..T
...
.K.
R..

output:

yes

result:

ok single line: 'yes'

Test #17:

score: 0
Accepted
time: 17ms
memory: 34852kb

input:

500 500
R..KK..................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #18:

score: 0
Accepted
time: 67ms
memory: 38084kb

input:

500 500
R..KK..................................................................................................................................................................................................................................................................................................

output:

yes

result:

ok single line: 'yes'

Test #19:

score: 0
Accepted
time: 67ms
memory: 46232kb

input:

742 741
KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...

output:

no

result:

ok single line: 'no'

Test #20:

score: 0
Accepted
time: 68ms
memory: 46560kb

input:

741 742
K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...

output:

no

result:

ok single line: 'no'

Test #21:

score: -100
Wrong Answer
time: 64ms
memory: 46196kb

input:

742 741
KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...

output:

no

result:

wrong answer 1st lines differ - expected: 'yes', found: 'no'