QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #575432 | #9108. Zayin and Obstacles | leafmaple# | AC ✓ | 203ms | 21820kb | C++20 | 2.1kb | 2024-09-19 14:16:22 | 2024-09-19 14:16:25 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
typedef double db;
typedef pair<int,int> pii;
typedef pair<db,db> pdd;
const int mod = 1e9 + 7;
const int inf = 1800000000000000000;
const int N = 1000005;
int n,m;
int f[105][105][105];
int dis[105][105][105];
int sx,sy,sz,ex,ey,ez;
int dx[6]={-1,1,0,0,0,0};
int dy[6]={0,0,-1,1,0,0};
int dz[6]={0,0,0,0,1,-1};
void bfs(){
queue<array<int,3>>q;
q.push({sx,sy,sz});
dis[sz][sx][sy]=0;
while(!q.empty()){
int x,y,z;
array<int,3> now = q.front();
x=now[0], y=now[1], z=now[2];
q.pop();
// cout<<now[0]<<' '<<now[1]<<' '<<now[2]<<endl;
for(int i=0;i<6;i++){
int nx,ny,nz;
nx=now[0]+dx[i];
ny=now[1]+dy[i];
nz=now[2]+dz[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&nz>=1&&nz<=n&&f[nz][nx][ny]==0){
// cout<<"fk"<<nx<<' '<<ny<<' '<<nz<<endl;
// cout<<dis[z][x][y]<<' '<<dis[nz][nx][ny]<<endl;
if(dis[z][x][y]+1<dis[nz][nx][ny]){
// cout<<111<<endl;
dis[nz][nx][ny]=dis[z][x][y]+1;
q.push({nx,ny,nz});
}
}
}
}
// cout<<"fk"<<endl;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++) f[i][j][k]=0,dis[i][j][k]=inf;
}
}
for(int i=1;i<=m;i++){
int a,b,c,d,e,ff;
cin>>a>>b>>c>>d>>e>>ff;
for(int h=c;h<=ff;h++){
f[h][a][b]+=1;
f[h][d+1][e+1]+=1;
f[h][a][e+1]-=1;
f[h][d+1][b]-=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
f[i][j][k]=f[i][j-1][k]+f[i][j][k-1]-f[i][j-1][k-1]+f[i][j][k];
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// for(int k=1;k<=n;k++){
// cout<<f[i][j][k]<<' ';
// }cout<<endl;
// }cout<<endl;
// }
cin>>sx>>sy>>sz>>ex>>ey>>ez;
bfs();
if(dis[ez][ex][ey]!=inf)
cout<<dis[ez][ex][ey]<<endl;
else cout<<-1<<endl;
}
signed main(){
IOS
int T;cin>>T;
while(T--){
solve();
}
}
//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
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7688kb
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: 18ms
memory: 21820kb
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: 38ms
memory: 21216kb
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: 17ms
memory: 21260kb
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: 29ms
memory: 21196kb
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: 203ms
memory: 21544kb
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