QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #504947 | #9108. Zayin and Obstacles | ikun# | AC ✓ | 139ms | 34620kb | C++20 | 1.4kb | 2024-08-04 17:42:58 | 2024-08-04 17:42:58 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include <cstring>
#include<queue>
#include<array>
using namespace std;
#define endl '\n'
#define int long long
int n,m;
int mp[110][110][110];
int s[110][110][110];
int x1,y1,z1,x2,y2,z2;
int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int dis[110][110][110];
void bfs()
{
queue<array<int,3>> q;
q.push({x1,y1,z1});
memset(dis,0x3f,sizeof dis);
dis[x1][y1][z1]=0;
while(q.size())
{
int x=q.front()[0];
int y=q.front()[1];
int z=q.front()[2];
q.pop();
for(int i=0;i<6;i++) {
int dx=x+dir[i][0];
int dy=y+dir[i][1];
int dz=z+dir[i][2];
if(dx>n||dy>n||dz>n||dx<1||dy<1||dz<1) continue;
if(dis[dx][dy][dz]>dis[x][y][z]+1 && !mp[dx][dy][dz])
{
dis[dx][dy][dz]=dis[x][y][z]+1;
q.push({dx,dy,dz});
}
}
}
}
void solve() {
cin>>n>>m;
memset(s,0,sizeof s);
for(int i=1;i<=m;i++) {
int a,b,c,d,e,f;
cin>>a>>b>>c>>d>>e>>f;
for(int j=a;j<=d;j++) {
for(int k=b;k<=e;k++){
s[j][k][c]++;
s[j][k][f+1]--;
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++)
mp[i][j][k]=mp[i][j][k-1]+s[i][j][k];
}
}
//
cin>>x1>>y1>>z1>>x2>>y2>>z2;
bfs();
if(dis[x2][y2][z2]>1e7)cout<<"-1\n";
else cout<<dis[x2][y2][z2]<<endl;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 25652kb
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: 21ms
memory: 33304kb
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: 54ms
memory: 34212kb
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: 135ms
memory: 34620kb
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: 27ms
memory: 33520kb
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: 139ms
memory: 34144kb
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