QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #674380 | #9108. Zayin and Obstacles | ucup-team5071# | AC ✓ | 191ms | 12732kb | C++20 | 2.1kb | 2024-10-25 15:29:20 | 2024-10-25 15:29:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> tii;
int fx[6]={1,-1,0,0,0,0};
int fy[6]={0,0,1,-1,0,0};
int fz[6]={0,0,0,0,1,-1};
int solve()
{
int n,k;cin>>n>>k;
vector<vector<vector<int>>> sum(n+2,vector<vector<int>>(n+2,vector<int>(n+2)));
vector<vector<vector<int>>> dis(n+2,vector<vector<int>>(n+2,vector<int>(n+2,-1)));
tii beg,ed;
for(int i=1;i<=k;i++){
int a,b,c,d,e,f,g;
cin>>a>>b>>c>>d>>e>>f;
for(auto x:{a,d+1})
for(auto y:{b,e+1})
for(auto z:{c,f+1}){
int tot=(x==a)+(y==b)+(z==c);
if(tot%2)sum[x][y][z]--;
else sum[x][y][z]++;
}
}
{
int a,b,c,d,e,f,g;
cin>>a>>b>>c>>d>>e>>f;
dis[a][b][c]=0;
beg=make_tuple(a,b,c);
ed=make_tuple(d,e,f);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]+=sum[i-1][j][k];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
sum[i][j][k]+=sum[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++){
sum[i][j][k]+=sum[i][j][k-1];
}
}
}
auto in = [&](int x,int y,int z){
return x>=1&&x<=n&&y>=1&&y<=n&&z>=1&&z<=n;
};
queue<tii> qu;
qu.push(beg);
while(!qu.empty()){
auto [x,y,z]=qu.front();qu.pop();
// cout<<"x="<<x<<" y="<<y<<" z="<<z<<" dis="<<dis[x][y][z]<<endl;;
for(int t=0;t<6;t++)if(int xx=x+fx[t],yy=y+fy[t],zz=z+fz[t];in(xx,yy,zz)&&sum[xx][yy][zz]==0&&dis[xx][yy][zz]==-1){
dis[xx][yy][zz]=dis[x][y][z]+1;
qu.push(make_tuple(xx,yy,zz));
}
}
return dis[get<0>(ed)][get<1>(ed)][get<2>(ed)];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;while(T--)cout<<solve()<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
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: 24ms
memory: 12100kb
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: 62ms
memory: 12044kb
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: 20ms
memory: 12160kb
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: 12132kb
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: 191ms
memory: 12732kb
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