QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#42323#168. Cube DividingafhiML 44ms40580kbC++2.4kb2022-08-01 22:16:262022-08-01 22:16:29

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-01 22:16:29]
  • Judged
  • Verdict: ML
  • Time: 44ms
  • Memory: 40580kb
  • [2022-08-01 22:16:26]
  • Submitted

answer

#include <bits/stdc++.h>

#define SZ(x) (int) x.size()
#define rep(i,a,b) for (int i = a;i < b;i++)

using ll = long long;

template<typename T> using V = std::vector<T>;

using std::cin;
using std::cout;
using std::cerr;

using vb = V<bool>;
using vvb = V<vb>;
using vvvb = V<vvb>;

void solve() {
    ll a,b,c,n;
    cin>>a>>b>>c>>n;
    V<int> xs{0,int(a) - 1},ys{0,int(b) - 1},zs{0,int(c) - 1};
    V<int> xx,yy,zz;
    for (int i = 0;i < n;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        xx.push_back(x);
        yy.push_back(y);
        zz.push_back(z);
        xs.push_back(x);
        xs.push_back(std::max(x - 1,0));
        xs.push_back(std::min(x + 1,(int)a - 1));
        ys.push_back(y);
        ys.push_back(std::max(y - 1,0));
        ys.push_back(std::min(y + 1,(int)b - 1));
        zs.push_back(z);
        zs.push_back(std::max(z - 1,0));
        zs.push_back(std::min(z + 1,(int)c - 1));
    }
    std::sort(xs.begin(),xs.end());
    xs.erase(std::unique(xs.begin(),xs.end()),xs.end());

    std::sort(ys.begin(),ys.end());
    ys.erase(std::unique(ys.begin(),ys.end()),ys.end());

    std::sort(zs.begin(),zs.end());
    zs.erase(std::unique(zs.begin(),zs.end()),zs.end());

    auto index = [] (const V<int>& ids,int v) {
        return (int) (std::lower_bound(ids.begin(),ids.end(),v) - ids.begin());
    };

    vvvb g(SZ(xs),vvb(SZ(ys),vb(SZ(zs))));

    for (int i = 0;i < n;i++) {
        g[index(xs,xx[i])][index(ys,yy[i])][index(zs,zz[i])] = true;
    }

    std::function<void(int,int,int)> dfs = [&] (int x,int y,int z) {
        if (x < 0 || y < 0 || z < 0 || x >= SZ(xs) || y >= SZ(ys) || z >= SZ(zs)) return;
        if (g[x][y][z]) return;
        g[x][y][z] = 1;
        dfs(x - 1,y,z);
        dfs(x + 1,y,z);
        dfs(x,y - 1,z);
        dfs(x,y + 1,z);
        dfs(x,y,z - 1);
        dfs(x,y,z + 1);
    };
    int cnt = 0;
    for (int x = 0;x < SZ(xs);x++) { 
        for (int y = 0;y < SZ(ys);y++) {
            for (int z = 0;z < SZ(zs);z++) {
                if (!g[x][y][z]) {
                    dfs(x,y,z);
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<'\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin.exceptions(cin.failbit);

#ifdef DEBUG
    freopen("input.txt","r",stdin);
#endif

    solve();

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3520kb

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: 2ms
memory: 3644kb

input:

3 3 3 1
1 1 1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

1 1 3 2
0 0 0
0 0 2

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 3ms
memory: 5888kb

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: 44ms
memory: 24820kb

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: 18ms
memory: 4444kb

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: 24ms
memory: 17948kb

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: 28ms
memory: 40580kb

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: 27ms
memory: 24156kb

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: 9ms
memory: 5468kb

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: 11ms
memory: 13280kb

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: 13ms
memory: 16108kb

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: 10ms
memory: 10572kb

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
Memory 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: