QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492784 | #168. Cube Dividing | Afterlife# | TL | 523ms | 59884kb | C++20 | 3.1kb | 2024-07-26 16:05:44 | 2024-07-26 16:05:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e3+7;
using P=tuple<int,int,int>;
set<P >key;
set<P >blk;
int A,B,C,n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>A>>B>>C;
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y,z;
cin>>x>>y>>z;
blk.insert({x,y,z});
}
for(auto [x,y,z]:blk)
{
for(auto dx:{-1,0,1})
for(auto dy:{-1,0,1})
for(auto dz:{-1,0,1})
{
if(x+dx<0||x+dx>=A||y+dy<0||y+dy>=B||z+dz<0||z+dz>=C)
continue;
key.insert({x+dx,y+dy,z+dz});
}
}
auto nkey=key;
for(auto [x,y,z]:key)
{
for(int S=0;S<8;S++)
{
for(int T=0;T<8;T++)
{
if(T!=(S&T))
continue;
int nx=x,ny=y,nz=z;
if(S&1)
nx=T&1?0:A-1;
if(S&2)
ny=T&1?0:B-1;
if(S&4)
nz=T&1?0:C-1;
nkey.insert({nx,ny,nz});
}
}
}
key.swap(nkey);
map<P,int> id;
for(auto p:key)
id[p]=id.size();
vector<int> fa(key.size()),isb(key.size());
for(auto x:blk)
isb[id[x]]=1;
iota(fa.begin(),fa.end(),0);
auto find=[&](auto self,const int &x)->int {
return x==fa[x]?x:fa[x]=self(self,fa[x]);
};
{
map<pair<int,int>,vector<pair<int,int> > >pts;
for(auto [p,w]:id)
{
auto [x,y,z]=p;
pts[{x,y}].push_back({z,w});
}
for(auto [nd,v]:pts)
{
sort(v.begin(),v.end());
for(int i=0;i+1<v.size();i++)
{
if(isb[v[i].second]||isb[v[i+1].second])
continue;
fa[find(find,v[i].second)]=find(find,v[i+1].second);
}
}
}
{
map<pair<int,int>,vector<pair<int,int> > >pts;
for(auto [p,w]:id)
{
auto [x,y,z]=p;
pts[{y,z}].push_back({x,w});
}
for(auto [nd,v]:pts)
{
sort(v.begin(),v.end());
for(int i=0;i+1<v.size();i++)
{
if(isb[v[i].second]||isb[v[i+1].second])
continue;
fa[find(find,v[i].second)]=find(find,v[i+1].second);
}
}
}
{
map<pair<int,int>,vector<pair<int,int> > >pts;
for(auto [p,w]:id)
{
auto [x,y,z]=p;
pts[{x,z}].push_back({y,w});
}
for(auto [nd,v]:pts)
{
sort(v.begin(),v.end());
for(int i=0;i+1<v.size();i++)
{
if(isb[v[i].second]||isb[v[i+1].second])
continue;
fa[find(find,v[i].second)]=find(find,v[i+1].second);
}
}
}
int ans=0;
for(int i=0;i<key.size();i++)
if(fa[i]==i&&!isb[i])
ans++;
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
2 2 2 4 0 0 0 1 1 0 1 0 1 0 1 1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 3 3 1 1 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 1 3 2 0 0 0 0 0 2
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 68ms
memory: 11060kb
input:
8 60 66 8004 4 49 31 0 38 42 0 45 22 1 19 23 1 36 47 6 9 15 7 55 18 4 24 51 4 34 31 0 31 64 5 24 23 0 48 34 6 30 12 6 41 22 3 6 51 3 43 34 4 49 39 5 31 5 3 36 63 5 37 21 4 11 55 6 53 41 6 51 56 6 42 9 4 59 55 3 30 49 5 15 32 3 59 64 5 7 32 2 42 60 3 0 27 7 5 41 3 34 45 5 39 57 3 24 36 0 16 13 1 55 3...
output:
15
result:
ok single line: '15'
Test #5:
score: 0
Accepted
time: 245ms
memory: 31040kb
input:
97 26 86 6966 67 4 0 63 2 45 30 1 66 37 12 70 54 10 50 61 13 14 82 10 29 76 20 42 66 14 45 8 19 65 2 0 63 42 19 24 11 21 23 65 2 56 65 24 61 33 15 17 51 0 26 2 19 51 7 21 38 53 15 57 73 13 42 38 13 10 78 22 52 83 15 14 68 13 55 50 5 62 70 0 17 56 2 84 93 13 29 44 6 40 58 13 1 15 17 66 38 21 59 2 16 ...
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 70ms
memory: 9848kb
input:
80 33 9 14465 35 15 4 24 9 4 59 30 8 18 15 6 64 2 4 54 5 6 49 29 1 38 12 8 1 5 4 29 23 0 70 25 5 26 15 2 11 18 7 47 30 5 37 30 3 54 29 1 73 23 5 22 31 8 31 28 7 4 11 2 65 10 8 64 15 1 25 31 7 58 2 5 72 2 2 49 15 3 50 18 5 36 22 1 19 21 7 29 31 6 31 25 0 54 30 3 15 24 1 7 18 7 38 6 7 57 20 8 32 16 0 ...
output:
857
result:
ok single line: '857'
Test #7:
score: 0
Accepted
time: 244ms
memory: 30220kb
input:
52 78 36 9942 35 64 32 40 33 27 9 69 5 24 3 19 46 30 5 40 11 5 47 28 13 15 56 30 1 1 2 43 24 35 48 31 33 49 13 31 35 36 2 25 45 0 14 67 26 30 52 23 1 45 13 3 47 0 7 40 28 21 0 4 19 64 8 32 26 17 19 29 12 7 8 24 42 3 15 21 39 11 35 41 13 47 28 22 18 5 18 40 67 23 36 75 12 35 21 10 16 59 0 25 13 10 51...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 523ms
memory: 59884kb
input:
51 84 87 15969 40 48 55 26 8 25 36 80 48 40 13 16 32 68 60 19 2 45 16 38 38 49 22 70 36 66 76 21 51 86 24 9 80 50 78 36 9 78 50 9 35 2 49 63 83 16 52 0 50 58 76 47 43 66 37 3 71 14 70 86 49 48 66 39 74 80 34 16 24 9 34 54 49 65 54 16 77 17 18 73 84 35 61 45 39 16 38 21 2 46 48 5 7 22 17 64 14 35 38 ...
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 388ms
memory: 43676kb
input:
58 55 66 17448 53 12 4 23 49 53 53 8 55 57 12 42 51 47 34 20 45 24 48 37 2 0 24 28 33 4 38 1 26 56 57 17 31 6 14 31 36 36 26 33 0 40 24 1 50 37 0 45 15 32 59 40 19 31 32 54 50 29 9 38 32 42 40 21 47 21 46 48 65 21 13 46 50 17 37 5 47 19 56 44 41 15 20 44 10 43 2 37 2 7 39 11 7 34 10 55 8 46 24 18 41...
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 81ms
memory: 11292kb
input:
31 49 22 14484 7 46 11 10 29 1 15 0 8 11 10 3 14 9 5 22 3 4 9 27 18 13 40 13 28 20 7 4 28 12 4 44 21 15 10 17 4 8 12 17 25 15 30 11 0 24 8 6 24 37 2 1 4 6 8 47 16 26 33 14 3 26 14 11 24 13 19 41 15 13 10 19 24 38 12 30 28 13 12 0 9 5 4 6 18 16 20 13 20 13 29 8 21 27 2 18 19 2 19 23 41 7 25 32 2 25 1...
output:
205
result:
ok single line: '205'
Test #11:
score: 0
Accepted
time: 168ms
memory: 22576kb
input:
65 36 42 8374 5 21 22 44 30 18 50 1 35 16 34 37 54 30 4 28 33 8 12 31 24 32 28 15 45 11 27 12 34 15 36 10 6 52 34 7 37 25 32 6 5 3 53 17 32 17 25 6 45 34 13 5 13 41 56 24 27 45 11 9 15 28 0 42 4 14 50 30 40 61 0 26 51 4 31 59 13 1 39 5 12 11 28 9 55 19 25 12 18 14 58 35 4 14 3 41 59 5 34 24 22 22 30...
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 124ms
memory: 17568kb
input:
24 49 106 3104 7 32 74 19 29 65 8 31 71 10 7 74 0 21 49 16 6 100 11 5 97 6 5 43 21 9 88 6 11 22 16 38 40 4 30 14 2 27 101 17 8 84 12 44 56 6 21 4 19 42 0 10 29 71 1 17 92 16 15 76 0 43 43 23 47 99 14 27 64 17 47 19 0 8 35 19 26 39 23 30 74 13 30 35 19 37 49 4 1 87 12 17 50 22 30 2 14 3 38 23 10 105 ...
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 129ms
memory: 18364kb
input:
14 92 57 6904 10 47 23 12 77 13 12 34 39 4 79 23 3 60 39 2 42 20 2 25 3 2 33 52 6 32 3 2 72 13 2 88 29 6 29 35 13 27 49 1 44 15 0 56 36 4 18 10 2 35 22 5 11 33 6 4 29 8 8 43 7 73 28 2 9 45 6 27 43 0 71 29 9 22 46 8 1 23 3 64 12 12 89 1 11 41 56 12 25 51 13 21 52 10 85 41 6 70 44 3 14 1 8 2 26 9 35 4...
output:
2
result:
ok single line: '2'
Test #14:
score: -100
Time Limit Exceeded
input:
883659 73120 315984 13620 356561 25749 95618 703272 39911 262803 491727 19022 72760 70333 17287 153234 97287 33099 183707 824073 26403 296847 810501 53197 224664 751333 40590 147652 477481 66750 310506 311528 62992 8676 89763 58901 253720 698886 31886 41966 514225 56832 252776 792753 51105 160521 14...