QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218891 | #2924. Lone Rook | ucup-team1004 | WA | 0ms | 3836kb | C++14 | 2.9kb | 2023-10-18 20:11:36 | 2023-10-18 20:11:37 |
Judging History
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;
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=-1,nex=-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=-1,nex=-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]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return 0;
return fa[x]=y,1;
}
bool valid(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=n;
}
void reach(int x,int y){
if(id[x][y])return;
id[x][y]=++k,fa[k]=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(Ry,Ry)=ban.getH(x,y),tie(Lx,Rx)=ban.getL(x,y);
if(~ly&&ly>Ly)merge(id[x][ly],id[x][y]);
if(~ry&&ry<Ry)merge(id[x][ry],id[x][y]);
if(~lx&&lx>Lx)merge(id[lx][y],id[x][y]);
if(~rx&&rx<Rx)merge(id[rx][y],id[x][y]);
ok.insert(x,y);
}
void remove(int x,int y){
ban.erase(x,y),reach(x,y);
}
void topo(){
queue<pair<int,int> >q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='K'&&!cnt[i][j]){
q.push({i,j}),remove(i,j);
}
}
}
for(int i,j;!q.empty();){
tie(i,j)=q.front(),q.pop();
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'){
q.push({x,y}),remove(x,y);
}else{
reach(x,y);
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
int sx=0,sy=0,tx=0,ty=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='S')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]&&a[i][j]=='.'){
reach(i,j);
}
}
}
topo();
puts(find(id[sx][sy])==find(id[tx][ty])?"yes":"no");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3836kb
input:
2 2 KR TK
output:
no
result:
wrong answer 1st lines differ - expected: 'yes', found: 'no'