QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#218962 | #2924. Lone Rook | ucup-team1004 | WA | 68ms | 46560kb | C++14 | 4.0kb | 2023-10-18 21:11:09 | 2023-10-18 21:11:09 |
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,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'