QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #465845 | #9108. Zayin and Obstacles | grass8cow# | AC ✓ | 184ms | 14464kb | C++17 | 1.5kb | 2024-07-07 11:33:59 | 2024-07-07 11:34:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,s[110][110][110],dis[110][110][110];
const int I=1e9;
void sol(){
memset(dis,0x3f,sizeof(dis));
memset(s,0,sizeof(s));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c,d,e,f;scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);d++,e++,f++;
for(int x=0;x<2;x++)for(int y=0;y<2;y++)for(int z=0;z<2;z++)
s[x?d:a][y?e:b][z?f:c]+=((x^y^z)?-1:1);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
s[i][j][k]+=s[i][j][k-1];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
s[i][j][k]+=s[i][j-1][k];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
s[i][j][k]+=s[i-1][j][k];
queue<array<int,3> >q;int x,y,z;
scanf("%d%d%d",&x,&y,&z);
q.push({x,y,z}),dis[x][y][z]=0;
scanf("%d%d%d",&x,&y,&z);
while(!q.empty()){
auto it=q.front();q.pop();
for(int i=0;i<3;i++)for(int o=-1;o<=1;o++){
int a=it[0]+((i==0)?o:0);
int b=it[1]+((i==1)?o:0);
int c=it[2]+((i==2)?o:0);
if(min(min(a,b),c)<=0)continue;
if(max(max(a,b),c)>n)continue;
if(s[a][b][c])continue;
if(dis[a][b][c]>I)
dis[a][b][c]=dis[it[0]][it[1]][it[2]]+1,
q.push({a,b,c});
}
}
if(dis[x][y][z]>I)puts("-1");
else printf("%d\n",dis[x][y][z]);
}
int main(){
int T;scanf("%d",&T);while(T--)sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14168kb
input:
3 3 0 1 1 1 3 3 3 3 1 2 1 1 2 3 3 1 1 1 3 3 3 3 3 2 1 1 2 2 3 1 1 2 2 3 2 1 2 2 3 3 2 1 1 1 1 1 3
output:
6 -1 14
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 19ms
memory: 14248kb
input:
5 19 27 2 1 1 2 18 19 4 2 1 4 19 19 6 1 1 6 18 19 8 2 1 8 19 19 10 1 1 10 18 19 12 2 1 12 19 19 14 1 1 14 18 19 16 2 1 16 19 19 18 1 1 18 18 19 1 1 2 18 19 2 2 1 4 19 19 4 1 1 6 18 19 6 2 1 8 19 19 8 1 1 10 18 19 10 2 1 12 19 19 12 1 1 14 18 19 14 2 1 16 19 19 16 1 1 18 18 19 18 1 2 2 19 19 2 1 2 4 ...
output:
1998 15998 53998 127998 249998
result:
ok 5 lines
Test #3:
score: 0
Accepted
time: 52ms
memory: 14464kb
input:
5 99 147 2 1 1 2 98 99 4 2 1 4 99 99 6 1 1 6 98 99 8 2 1 8 99 99 10 1 1 10 98 99 12 2 1 12 99 99 14 1 1 14 98 99 16 2 1 16 99 99 18 1 1 18 98 99 20 2 1 20 99 99 22 1 1 22 98 99 24 2 1 24 99 99 26 1 1 26 98 99 28 2 1 28 99 99 30 1 1 30 98 99 32 2 1 32 99 99 34 1 1 34 98 99 36 2 1 36 99 99 38 1 1 38 9...
output:
132878 2596 227782 37198 90672
result:
ok 5 lines
Test #4:
score: 0
Accepted
time: 14ms
memory: 14260kb
input:
5 99 1000 2 1 1 2 98 99 4 2 1 4 99 99 6 1 1 6 98 99 8 2 1 8 99 99 10 1 1 10 98 99 12 2 1 12 99 99 14 1 1 14 98 99 16 2 1 16 99 99 18 1 1 18 98 99 20 2 1 20 99 99 22 1 1 22 98 99 24 2 1 24 99 99 26 1 1 26 98 99 28 2 1 28 99 99 30 1 1 30 98 99 32 2 1 32 99 99 34 1 1 34 98 99 36 2 1 36 99 99 38 1 1 38 ...
output:
4998 4998 4998 4998 4998
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 32ms
memory: 14164kb
input:
5 19 1000 2 1 1 2 18 19 4 2 1 4 19 19 6 1 1 6 18 19 8 2 1 8 19 19 10 1 1 10 18 19 12 2 1 12 19 19 14 1 1 14 18 19 16 2 1 16 19 19 18 1 1 18 18 19 4 13 10 4 19 12 6 5 5 6 6 18 6 16 4 6 18 11 8 6 10 8 17 19 14 10 7 14 17 12 2 4 4 2 5 15 4 5 10 4 7 17 12 1 2 12 2 9 12 8 10 12 18 15 16 19 2 16 19 8 8 1 ...
output:
-1 798 1906 3198 4998
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 184ms
memory: 14348kb
input:
5 100 0 92 81 37 11 85 14 100 0 16 48 91 61 65 58 100 0 87 25 52 83 7 45 100 0 80 95 16 62 5 80 100 0 33 33 50 48 82 3
output:
108 95 29 172 111
result:
ok 5 lines