QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#492784#168. Cube DividingAfterlife#TL 523ms59884kbC++203.1kb2024-07-26 16:05:442024-07-26 16:05:45

Judging History

This is the latest submission verdict.

  • [2024-07-26 16:05:45]
  • Judged
  • Verdict: TL
  • Time: 523ms
  • Memory: 59884kb
  • [2024-07-26 16:05:44]
  • Submitted

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";
}

詳細信息

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...

output:


result: