QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #772916 | #1493. Push a Box | I_be_wanna | 100 ✓ | 125ms | 77384kb | C++17 | 10.5kb | 2024-11-22 22:55:44 | 2024-11-22 22:55:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1551,M=N*N;
int n,m,Q,S,T,nm;
char s[M];
int dir[4];
bool f[M][4];
inline int id(int x,int y){return x*(m+1)+y;}
int dfn[M],st[M],tp,low[M],cntdfn,scc,fa[M<<1];
inline void tarjan(int x,int lst){
dfn[x]=low[x]=++cntdfn;
st[++tp]=x;
for(int i=0;i<4;i++)if(i^lst){
int y=x+dir[i];
if(s[y]!='.')continue;
if(!dfn[y]){
tarjan(y,i^1);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
scc++;
fa[nm+scc]=x;
while(st[tp]!=y){
fa[st[tp]]=nm+scc;
tp--;
}
tp--;
fa[y]=nm+scc;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
inline bool reach(int x,int y){return fa[x]==fa[y]||fa[fa[x]]==y||fa[fa[y]]==x;}
namespace step1{
bool vis[M];
inline void solve(){
queue<int>q;
vis[S]=vis[T]=1;
q.push(S);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<4;i++){
int y=x+dir[i];
if(s[y]=='.'&&!vis[y])q.push(y),vis[y]=1;
}
}
}
}
inline void solve(){
queue<pair<int,int> >q;
for(int i=0;i<4;i++){
int x=T+dir[i^1];
if(step1::vis[x])f[T][i]=1,q.push({T,i});
}
while(!q.empty()){
int x=q.front().first,d=q.front().second;
q.pop();
int y=x+dir[d];
if(s[y]=='.'&&!f[y][d]){
f[y][d]=1;
q.push({y,d});
}
int lst=x+dir[d^1];
for(int i=0;i<4;i++)if(!f[x][i]){
int y=x+dir[i^1];
if(s[y]=='.'&&reach(lst,y)){
f[x][i]=1;
q.push({x,i});
}
}
}
}
inline bool solve(int x){
if(x==T)return 1;
for(int i=0;i<4;i++)if(f[x][i])return 1;
return 0;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m>>Q;
nm=(n+1)*(m+1);
dir[0]=-m-1,dir[1]=m+1,dir[2]=-1,dir[3]=1;
for(int i=1;i<=n;i++){
cin>>(s+i*(m+1)+1);
for(int j=i*(m+1)+1;j<=i*(m+1)+m;j++){
if(s[j]=='A')S=j,s[j]='.';
else if(s[j]=='B')T=j,s[j]='.';
}
}
tarjan(S,-1);
step1::solve();
solve();
// for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<solve(id(i,j))<<" \n"[j==m];
while(Q--){
int x,y;
cin>>x>>y;
if(solve(id(x,y)))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
const int N=1551,M=N*N;
int n,m,Q,S,T,nm;
char s[M];
int dir[4];
bool f[M][4];
inline int id(int x,int y){return x*(m+1)+y;}
int dfn[M],st[M],tp,low[M],cntdfn,scc,fa[M<<1];
inline void tarjan(int x,int lst){
dfn[x]=low[x]=++cntdfn;
st[++tp]=x;
for(int i=0;i<4;i++)if(i^lst){
int y=x+dir[i];
if(s[y]!='.')continue;
if(!dfn[y]){
tarjan(y,i^1);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
scc++;
fa[nm+scc]=x;
while(st[tp]!=y){
fa[st[tp]]=nm+scc;
tp--;
}
tp--;
fa[y]=nm+scc;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
inline bool reach(int x,int y){return fa[x]==fa[y]||fa[fa[x]]==y||fa[fa[y]]==x;}
namespace step1{
bool vis[M];
inline void solve(){
queue<int>q;
vis[S]=vis[T]=1;
q.push(S);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<4;i++){
int y=x+dir[i];
if(s[y]=='.'&&!vis[y])q.push(y),vis[y]=1;
}
}
}
}
inline void solve(){
queue<pair<int,int> >q;
for(int i=0;i<4;i++){
int x=T+dir[i^1];
if(step1::vis[x])f[T][i]=1,q.push({T,i});
}
while(!q.empty()){
int x=q.front().first,d=q.front().second;
q.pop();
int y=x+dir[d];
if(s[y]=='.'&&!f[y][d]){
f[y][d]=1;
q.push({y,d});
}
int lst=x+dir[d^1];
for(int i=0;i<4;i++)if(!f[x][i]){
int y=x+dir[i^1];
if(s[y]=='.'&&reach(lst,y)){
f[x][i]=1;
q.push({x,i});
}
}
}
}
inline bool solve(int x){
if(x==T)return 1;
for(int i=0;i<4;i++)if(f[x][i])return 1;
return 0;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m>>Q;
nm=(n+1)*(m+1);
dir[0]=-m-1,dir[1]=m+1,dir[2]=-1,dir[3]=1;
for(int i=1;i<=n;i++){
cin>>(s+i*(m+1)+1);
for(int j=i*(m+1)+1;j<=i*(m+1)+m;j++){
if(s[j]=='A')S=j,s[j]='.';
else if(s[j]=='B')T=j,s[j]='.';
}
}
tarjan(S,-1);
step1::solve();
solve();
// for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<solve(id(i,j))<<" \n"[j==m];
while(Q--){
int x,y;
cin>>x>>y;
if(solve(id(x,y)))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
const int N=1551,M=N*N;
int n,m,Q,S,T,nm;
char s[M];
int dir[4];
bool f[M][4];
inline int id(int x,int y){return x*(m+1)+y;}
int dfn[M],st[M],tp,low[M],cntdfn,scc,fa[M<<1];
inline void tarjan(int x,int lst){
dfn[x]=low[x]=++cntdfn;
st[++tp]=x;
for(int i=0;i<4;i++)if(i^lst){
int y=x+dir[i];
if(s[y]!='.')continue;
if(!dfn[y]){
tarjan(y,i^1);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
scc++;
fa[nm+scc]=x;
while(st[tp]!=y){
fa[st[tp]]=nm+scc;
tp--;
}
tp--;
fa[y]=nm+scc;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
inline bool reach(int x,int y){return fa[x]==fa[y]||fa[fa[x]]==y||fa[fa[y]]==x;}
namespace step1{
bool vis[M];
inline void solve(){
queue<int>q;
vis[S]=vis[T]=1;
q.push(S);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<4;i++){
int y=x+dir[i];
if(s[y]=='.'&&!vis[y])q.push(y),vis[y]=1;
}
}
}
}
inline void solve(){
queue<pair<int,int> >q;
for(int i=0;i<4;i++){
int x=T+dir[i^1];
if(step1::vis[x])f[T][i]=1,q.push({T,i});
}
while(!q.empty()){
int x=q.front().first,d=q.front().second;
q.pop();
int y=x+dir[d];
if(s[y]=='.'&&!f[y][d]){
f[y][d]=1;
q.push({y,d});
}
int lst=x+dir[d^1];
for(int i=0;i<4;i++)if(!f[x][i]){
int y=x+dir[i^1];
if(s[y]=='.'&&reach(lst,y)){
f[x][i]=1;
q.push({x,i});
}
}
}
}
inline bool solve(int x){
if(x==T)return 1;
for(int i=0;i<4;i++)if(f[x][i])return 1;
return 0;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m>>Q;
nm=(n+1)*(m+1);
dir[0]=-m-1,dir[1]=m+1,dir[2]=-1,dir[3]=1;
for(int i=1;i<=n;i++){
cin>>(s+i*(m+1)+1);
for(int j=i*(m+1)+1;j<=i*(m+1)+m;j++){
if(s[j]=='A')S=j,s[j]='.';
else if(s[j]=='B')T=j,s[j]='.';
}
}
tarjan(S,-1);
step1::solve();
solve();
// for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<solve(id(i,j))<<" \n"[j==m];
while(Q--){
int x,y;
cin>>x>>y;
if(solve(id(x,y)))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
const int N=1551,M=N*N;
int n,m,Q,S,T,nm;
char s[M];
int dir[4];
bool f[M][4];
inline int id(int x,int y){return x*(m+1)+y;}
int dfn[M],st[M],tp,low[M],cntdfn,scc,fa[M<<1];
inline void tarjan(int x,int lst){
dfn[x]=low[x]=++cntdfn;
st[++tp]=x;
for(int i=0;i<4;i++)if(i^lst){
int y=x+dir[i];
if(s[y]!='.')continue;
if(!dfn[y]){
tarjan(y,i^1);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
scc++;
fa[nm+scc]=x;
while(st[tp]!=y){
fa[st[tp]]=nm+scc;
tp--;
}
tp--;
fa[y]=nm+scc;
}
}
else low[x]=min(low[x],dfn[y]);
}
}
inline bool reach(int x,int y){return fa[x]==fa[y]||fa[fa[x]]==y||fa[fa[y]]==x;}
namespace step1{
bool vis[M];
inline void solve(){
queue<int>q;
vis[S]=vis[T]=1;
q.push(S);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<4;i++){
int y=x+dir[i];
if(s[y]=='.'&&!vis[y])q.push(y),vis[y]=1;
}
}
}
}
inline void solve(){
queue<pair<int,int> >q;
for(int i=0;i<4;i++){
int x=T+dir[i^1];
if(step1::vis[x])f[T][i]=1,q.push({T,i});
}
while(!q.empty()){
int x=q.front().first,d=q.front().second;
q.pop();
int y=x+dir[d];
if(s[y]=='.'&&!f[y][d]){
f[y][d]=1;
q.push({y,d});
}
int lst=x+dir[d^1];
for(int i=0;i<4;i++)if(!f[x][i]){
int y=x+dir[i^1];
if(s[y]=='.'&&reach(lst,y)){
f[x][i]=1;
q.push({x,i});
}
}
}
}
inline bool solve(int x){
if(x==T)return 1;
for(int i=0;i<4;i++)if(f[x][i])return 1;
return 0;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>m>>Q;
nm=(n+1)*(m+1);
dir[0]=-m-1,dir[1]=m+1,dir[2]=-1,dir[3]=1;
for(int i=1;i<=n;i++){
cin>>(s+i*(m+1)+1);
for(int j=i*(m+1)+1;j<=i*(m+1)+m;j++){
if(s[j]=='A')S=j,s[j]='.';
else if(s[j]=='B')T=j,s[j]='.';
}
}
tarjan(S,-1);
step1::solve();
solve();
// for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<solve(id(i,j))<<" \n"[j==m];
while(Q--){
int x,y;
cin>>x>>y;
if(solve(id(x,y)))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 6.66667
Accepted
time: 0ms
memory: 11860kb
input:
5 5 4 ##.## ##.## A.B.. ##.## ##.## 3 2 3 5 1 3 5 3
output:
NO YES NO NO
result:
ok 4 lines
Test #2:
score: 6.66667
Accepted
time: 2ms
memory: 11760kb
input:
5 5 16 ..... .###. .#.#. A.B.. ##.## 1 1 1 2 1 3 1 4 1 5 2 1 2 5 3 1 3 3 3 5 4 1 4 2 4 3 4 4 4 5 5 3
output:
NO NO NO NO NO NO NO NO NO NO YES YES YES YES YES NO
result:
ok 16 lines
Test #3:
score: 6.66667
Accepted
time: 1ms
memory: 9972kb
input:
5 5 15 ...## A.### .#... ##..B ##... 1 1 1 2 1 3 2 1 2 2 3 1 3 3 3 4 3 5 4 3 4 4 4 5 5 3 5 4 5 5
output:
NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO
result:
ok 15 lines
Test #4:
score: 6.66667
Accepted
time: 1ms
memory: 11968kb
input:
41 46 100 ..#.....##.#...............#.#.#...#.......... .#...###.###.#######.#.#.#####.#.#.#..##.#.#.# .......#...#.............#...........#.#.#.#.. .#.#.#.#####.#.#.###.#.#.#.#.###.#.#.#.#.#.#.# .#.......#.#.............#...............#.#.. ####.###.#..##.#.#.###.#.###.#.#.#####.#.#.### .#...#.#...
output:
YES YES NO YES NO NO NO NO NO NO YES NO NO YES NO NO NO NO YES NO YES NO NO YES NO YES NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO YES NO NO YES NO NO NO YES YES YES YES YES NO NO YES NO NO NO YES YES NO YES NO NO YES NO NO YES NO NO YES NO NO NO YES YES N...
result:
ok 100 lines
Test #5:
score: 6.66667
Accepted
time: 1ms
memory: 11764kb
input:
24 31 100 .#.#.#.#.......#.............#. .###.#.#.#.#####.#.#.#.#.###.#. .#...#.....#.#.A............... .#.###.#.###.#.#.#.###.######## ...#.#.....#...#.........#..... .#####.#.###.#.#.###...#.###.#. ......##.#.....#.#.......#..... ..####.#.#.#####.###.#.#.###### ...#.........#.#.#...#...#...#. .#...
output:
NO NO NO YES NO NO NO NO YES YES NO NO NO YES NO NO YES NO NO NO NO YES NO NO YES YES NO NO YES YES NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO YES YES NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO YES YES NO NO YES YES NO NO NO YES NO NO NO YES NO NO NO NO NO YES YES NO YES YES NO NO YES NO ...
result:
ok 100 lines
Test #6:
score: 6.66667
Accepted
time: 107ms
memory: 72760kb
input:
1500 1500 50000 .....#...#.........#...#...#.#.................#....#....#...#...#...................#.#.....#.#.#...........#.#...#.........#.........#.#...#.....#.............#.#...#.....#.....#...#.#...........#..#........#...#...#...#.....#.........#.....#.#.#.....#.........##......#.#.......#.#...
output:
NO NO NO NO NO NO NO YES NO NO YES YES NO NO NO NO NO NO YES YES NO NO YES NO NO NO YES NO NO NO YES NO NO NO NO NO NO YES NO YES NO NO NO YES NO NO NO NO YES YES NO NO YES NO NO YES YES NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO YES NO YES NO YES NO NO NO NO NO YES NO NO N...
result:
ok 50000 lines
Test #7:
score: 6.66667
Accepted
time: 99ms
memory: 70248kb
input:
1500 1500 50000 ...................#.......#.#.....#...#.#...#.................#.#..#................#.#.....#...#.....##............#.#.#.....#.......#.......#...#.........#.#...#.........#.........#...........#...#.................#.#.......#........#..........#...#.......#.............#.............
output:
NO YES NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 50000 lines
Test #8:
score: 6.66667
Accepted
time: 101ms
memory: 72808kb
input:
1500 1500 50000 .....#.........#.....#.#...###...........#...........#.............#.........#.#.#.............................#.#.......#...#.#.....#......#...........##.......##........#.#.#...#................##.#.......#.......................#.#.........#.........#.......#.....##..#.#...#.........
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO...
result:
ok 50000 lines
Test #9:
score: 6.66667
Accepted
time: 125ms
memory: 76136kb
input:
1500 1500 50000 ...#.#.....#.#...........#...#...#.#...#.......#...#...................................#..#..#.#.......#.....#.....#.........#.......#.......#.#.........#...#.....#.#.....#.....#.......#.......#.........#.....#.###.............#...#.....#...#...#.....#.........#.#...#...........#.......
output:
NO NO YES YES YES NO YES NO NO NO YES NO YES NO NO NO NO YES YES YES NO YES NO NO NO NO NO NO NO NO YES YES NO NO NO YES NO YES NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO YES NO NO YES YES NO NO NO YES YES YES NO YES NO YES YES YES NO NO YES YES NO NO YES YES YES NO YES NO NO NO NO YES NO YES NO...
result:
ok 50000 lines
Test #10:
score: 6.66667
Accepted
time: 95ms
memory: 77384kb
input:
1500 1500 50000 .....#...#.......#....##...........#.#...#.....#..#........#.#.#.##....##..#.#.............#.#......##.#...............#.#.#...#.#.#.#...#.#...#.........#.....#.......#.......###...##........#...#.#.#.....#.#.#.#.#...#.................#.#.............#.###...#.......#...#.#...#.#.......
output:
NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES YES NO YES NO NO NO YES NO YES NO NO YES NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES ...
result:
ok 50000 lines
Test #11:
score: 6.66667
Accepted
time: 97ms
memory: 73868kb
input:
1500 1500 50000 .#...#...........#...............#...#.........#...............#.......#.#.........................#...........#.#.......#..............##.....#...#.#.....#...#.#.#...#.#...#.....#.#.#...............#...........#.#..#....#.............#...#...#.....#.....#...............#.....#.........
output:
NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES...
result:
ok 50000 lines
Test #12:
score: 6.66667
Accepted
time: 93ms
memory: 75752kb
input:
1500 1500 50000 .#.....#...#.#.#...#...#.#.#...#.#....#....#.#.....#.................#.....#...#.#.......#...#..##.....#.....#...#.#...............#.#...#.#...#.....................#...#.....#.#.....#.....#.#.#.....#..........##..#..#.........#.#..##...#.....#...#...#.................#...#.#......#....
output:
NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO YES NO NO NO YES NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO YES NO NO NO N...
result:
ok 50000 lines
Test #13:
score: 6.66667
Accepted
time: 116ms
memory: 74804kb
input:
1500 1500 50000 ...........#...#.#.#.......#...#.....#...#.....#.#.....................................#.#.#..............##.#.............##....#.#.................#.........#..#............#.......#.....##....#...#.....#.#...........#.........#...#.#.....#.#.......#.#.......#...........#...#.#.......
output:
NO NO NO YES NO NO YES NO NO NO NO NO YES NO NO NO YES NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO YES NO NO NO NO NO NO NO NO YES YES YES YES YES NO NO YES NO NO NO NO YES YES NO NO NO YES YES NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO N...
result:
ok 50000 lines
Test #14:
score: 6.66667
Accepted
time: 79ms
memory: 71736kb
input:
1500 1500 50000 .........#...#...........#.....#.#...#.............#.#.#...#.........#.............#.#...#.#...#.....#.....#.........#...#.#...#...#...........#.....#.....#.#...#...#....#....#.#.#...........#.....#...............#.....#...#...#.#......#........#...#.....#.......#.#.....#...#.#.........
output:
NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO YES NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO N...
result:
ok 50000 lines
Test #15:
score: 6.66667
Accepted
time: 111ms
memory: 71428kb
input:
1500 1500 50000 ............##.......#.....#.....#...#...#...#.#.#.#.........#.#.......#.....#.#...#...#.......#.....#.#...........#...#.#.......#...#...#.#...#.....#...#...#.....#......##.#.....#.#...............##....##..#...#...#...........#.......#.....#................#...#....#.#.......#..#..#...
output:
NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 50000 lines