QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629247#4635. Graph Operationlwm7708WA 72ms4204kbC++178.6kb2024-10-11 09:46:202024-10-11 09:46:20

Judging History

你现在查看的是最新测评结果

  • [2024-10-11 09:46:20]
  • 评测
  • 测评结果：WA
  • 用时：72ms
  • 内存：4204kb
查看
  • [2024-10-11 09:46:20]
  • 提交

answer

#include <algorithm>
#include <array>
#include <cstdint>
#include <ios>
#include <iostream>
#include <vector>

class bitset {

private:

    using blk_t = std::uint64_t;

    std::int32_t sz;
    std::int32_t blks;
    blk_t mask;

public:

    class reference {

    private:

        blk_t& blk;
        blk_t mask;

    public:

        explicit reference(blk_t& blk, std::int32_t bit) : blk(blk), mask(blk_t(1) << bit) {}

        operator bool() const {

            return (blk & mask) != 0;

        }

        void operator=(bool x) {

            if (!x) {
                blk &= ~mask;
            } else {
                blk |= mask;
            }

        }

    };

    std::vector<blk_t> data;

    explicit bitset() : bitset(0) {}

    explicit bitset(
        std::int32_t sz
    ) : sz(sz), blks((sz + 63) / 64), mask((sz % 64 ? blk_t(1) << (sz % 64) : 0) - 1), data(blks) {}

    reference operator[](std::int32_t pos) {

        return reference(data[pos / 64], pos % 64);

    }

    bool operator[](std::int32_t pos) const {

        return (data[pos / 64] >> (pos % 64) & 1) == 1;

    }

    bitset operator~() const {

        bitset res = *this;

        res.flip();

        return res;

    }

    void operator&=(const bitset& other) {

        for (std::int32_t i = 0; i < blks; ++i) {
            data[i] &= other.data[i];
        }

    }

    void operator|=(const bitset& other) {

        for (std::int32_t i = 0; i < blks; ++i) {
            data[i] |= other.data[i];
        }

    }

    void operator^=(const bitset& other) {

        for (std::int32_t i = 0; i < blks; ++i) {
            data[i] ^= other.data[i];
        }

    }

    void operator<<=(std::int32_t pos) {

        if (pos >= sz) {
            reset();
            return;
        }

        const std::int32_t bits = pos % 64;
        const std::int32_t shft = pos / 64;

        for (std::int32_t i = blks - 1; i >= shft; --i) {
            data[i] = data[i - shft] << bits;
            if (bits && i > shft) {
                data[i] |= data[i - shft - 1] >> (64 - bits);
            }
        }

        std::fill_n(std::begin(data), shft, 0);

    }

    void operator>>=(std::int32_t pos) {

        if (pos >= sz) {
            reset();
            return;
        }

        data[blks - 1] &= mask;

        const std::int32_t bits = pos % 64;
        const std::int32_t shft = pos / 64;

        for (std::int32_t i = 0; i < blks - shft; ++i) {
            data[i] = data[i + shft] >> bits;
            if (bits && i < blks - shft - 1) {
                data[i] |= data[i + shft + 1] << (64 - bits);
            }
        }

        std::fill(std::end(data) - shft, std::end(data), 0);

    }

    bool all() const {

        for (std::int32_t i = 0; i < blks - 1; ++i) {
            if (~data[i]) {
                return false;
            }
        }

        return (data[blks - 1] & mask) == mask;

    }

    bool any() const {

        for (std::int32_t i = 0; i < blks - 1; ++i) {
            if (data[i]) {
                return true;
            }
        }

        return (data[blks - 1] & mask) != 0;

    }

    std::int32_t count() const {

        std::int32_t bits = __builtin_popcountll(data[blks - 1] & mask);

        for (std::int32_t i = 0; i < blks - 1; ++i) {
            bits += __builtin_popcountll(data[i]);
        }

        return bits;

    }

    void flip() {

        for (auto& x : data) {
            x ^= ~blk_t();
        }

    }

    bool none() const {

        return !any();

    }

    void reset() {

        std::fill_n(std::begin(data), blks, 0);

    }

    void set() {

        std::fill_n(std::begin(data), blks, ~blk_t());

    }

    std::int32_t size() const {

        return sz;

    }

    friend bool operator==(const bitset& lhs, const bitset& rhs) {

        if (lhs.sz != rhs.sz) {
            return false;
        }

        const std::int32_t len = lhs.blks;

        if (len == 0) {
            return true;
        }

        const std::vector<blk_t>& data_l = lhs.data;
        const std::vector<blk_t>& data_r = rhs.data;

        return std::equal(
            std::begin(data_l), std::begin(data_l) + len - 1, std::begin(data_r)
        ) && ((data_l[len - 1] ^ data_r[len - 1]) & lhs.mask) == 0;

    }

    friend bool operator!=(const bitset& lhs, const bitset& rhs) {

        return !(lhs == rhs);

    }

    friend bitset operator&(bitset lhs, const bitset& rhs) {

        lhs &= rhs;

        return lhs;

    }

    friend bitset operator|(bitset lhs, const bitset& rhs) {

        lhs |= rhs;

        return lhs;

    }

    friend bitset operator^(bitset lhs, const bitset& rhs) {

        lhs ^= rhs;

        return lhs;

    }

    friend bitset operator<<(bitset lhs, std::int32_t pos) {

        lhs <<= pos;

        return lhs;

    }

    friend bitset operator>>(bitset lhs, std::int32_t pos) {

        lhs >>= pos;

        return lhs;

    }

};

void solve() {

    using op = std::array<std::int32_t, 4>;

    std::int32_t m;
    std::int32_t n;

    std::cin >> n >> m;

    std::vector g_adj(n, bitset(n));

    for (std::int32_t i = 0; i < m; ++i) {
        std::int32_t u;
        std::int32_t v;
        std::cin >> u >> v;
        --u;
        --v;
        g_adj[u][v] = true;
        g_adj[v][u] = true;
    }

    std::vector h_adj(n, bitset(n));

    for (std::int32_t i = 0; i < m; ++i) {
        std::int32_t u;
        std::int32_t v;
        std::cin >> u >> v;
        --u;
        --v;
        h_adj[u][v] = true;
        h_adj[v][u] = true;
    }

    for (std::int32_t i = 0; i < n; ++i) {
        if (g_adj[i].count() != h_adj[i].count()) {
            std::cout << -1 << '\n';
            return;
        }
    }

    std::vector<op> g_ops;
    std::vector<op> h_ops;

    for (std::int32_t i = 0; i < n; ++i) {
        std::vector<std::int32_t> nodes_1;
        std::vector<std::int32_t> nodes_2;
        nodes_1.reserve(n / 2);
        nodes_2.reserve(n / 2);
        for (std::int32_t j = 0; j < n; ++j) {
            if (g_adj[i][j] && !h_adj[i][j]) {
                nodes_1.push_back(j);
            } else if (!g_adj[i][j] && h_adj[i][j]) {
                nodes_2.push_back(j);
            }
        }
        while (!std::empty(nodes_1)) {
            const auto apply = [](std::vector<bitset>& adj, const op& c_op) -> void {
                adj[c_op[0]][c_op[1]] = false;
                adj[c_op[1]][c_op[0]] = false;
                adj[c_op[2]][c_op[3]] = false;
                adj[c_op[3]][c_op[2]] = false;
                adj[c_op[0]][c_op[2]] = true;
                adj[c_op[2]][c_op[0]] = true;
                adj[c_op[1]][c_op[3]] = true;
                adj[c_op[3]][c_op[1]] = true;
            };
            const std::int32_t node_1 = nodes_1.back();
            const std::int32_t node_2 = nodes_2.back();
            bitset st = ~g_adj[node_1] & g_adj[node_2];
            st[node_1] = false;
            if (st.count()) {
                std::int32_t node = 0;
                while (st.data[node / 64] == 0) {
                    node += 64;
                }
                while (!st[node]) {
                    ++node;
                }
                g_ops.push_back(op({i, node_1, node_2, node}));
                apply(g_adj, g_ops.back());
            } else {
                st = h_adj[node_1] & ~h_adj[node_2];
                st[node_2] = false;
                std::int32_t node = 0;
                while (st.data[node / 64] == 0) {
                    node += 64;
                }
                while (!st[node]) {
                    ++node;
                }
                h_ops.push_back(op({i, node_2, node_1, node}));
                apply(h_adj, h_ops.back());
            }
            nodes_1.pop_back();
            nodes_2.pop_back();
        }
    }

    std::cout << std::size(g_ops) + std::size(h_ops) << '\n';

    for (const auto& [a, b, c, d] : g_ops) {
        std::cout << a + 1 << ' ' << b + 1 << ' ' << c + 1 << ' ' << d + 1 << '\n';
    }

    std::reverse(std::begin(h_ops), std::end(h_ops));

    for (const auto& [a, b, c, d] : h_ops) {
        std::cout << a + 1 << ' ' << c + 1 << ' ' << b + 1 << ' ' << d + 1 << '\n';
    }

}

int main() {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

4 2
1 2
3 4
1 3
2 4

output:

1
1 2 3 4

result:

ok n=4

Test #2:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

6 12
1 2
3 5
4 6
1 4
1 5
1 6
2 3
2 5
2 6
3 4
3 6
4 5
1 3
2 4
5 6
1 4
1 5
1 6
2 3
2 5
2 6
3 4
3 6
4 5

output:

2
1 2 3 4
3 5 4 6

result:

ok n=6

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

4 0

output:

0

result:

ok n=4

Test #4:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

10 0

output:

0

result:

ok n=10

Test #5:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

100 0

output:

0

result:

ok n=100

Test #6:

score: 0
Accepted
time: 0ms
memory: 4204kb

input:

1000 0

output:

0

result:

ok n=1000

Test #7:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

4 6
4 1
1 2
1 3
4 3
3 2
4 2
4 1
4 2
4 3
3 2
1 3
1 2

output:

0

result:

ok n=4

Test #8:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

10 45
7 5
6 1
3 8
9 7
8 1
2 1
7 1
10 9
4 5
6 5
8 6
3 1
5 1
3 6
4 9
6 9
9 1
10 6
4 6
10 2
4 7
4 8
2 5
10 5
3 4
3 7
10 8
8 2
3 10
4 1
4 2
2 9
2 7
8 7
10 1
8 5
6 7
2 6
10 7
9 5
3 9
3 5
8 9
3 2
4 10
3 5
4 6
9 5
7 5
2 9
6 5
4 5
4 1
3 10
8 9
8 6
10 7
3 9
8 2
9 7
8 7
10 8
10 1
2 7
3 6
2 6
3 2
4 2
2 5
10 9
...

output:

0

result:

ok n=10

Test #9:

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

input:

100 4950
15 37
36 56
57 64
66 63
35 70
8 65
25 36
1 27
6 74
79 22
35 34
79 70
53 74
41 63
7 40
41 22
99 93
96 70
35 30
20 67
48 65
100 21
8 4
75 87
80 10
82 38
7 10
85 77
42 77
28 64
73 60
20 74
73 86
24 31
73 44
97 93
8 74
48 19
63 42
41 57
25 79
13 19
96 39
59 44
81 20
66 2
8 37
34 23
88 27
12 14
...

output:

0

result:

ok n=100

Test #10:

score: 0
Accepted
time: 72ms
memory: 3968kb

input:

1000 499500
90 844
735 814
874 452
191 64
745 192
489 653
998 227
104 125
296 644
285 190
831 763
70 776
981 126
213 964
306 137
199 965
849 5
717 70
329 305
196 836
909 527
222 367
323 554
384 900
496 797
620 860
18 823
929 135
589 207
947 354
461 271
22 914
456 403
263 362
908 870
30 384
995 996
3...

output:

0

result:

ok n=1000

Test #11:

score: 0
Accepted
time: 66ms
memory: 3912kb

input:

1000 499500
561 780
496 694
698 721
598 412
55 527
799 952
790 473
980 139
375 308
605 850
670 77
77 908
958 436
379 504
293 452
735 666
223 901
944 455
554 123
644 817
723 68
157 867
527 755
380 937
904 851
614 666
299 131
369 83
61 651
820 239
432 583
588 869
500 542
502 996
305 43
601 882
277 337...

output:

0

result:

ok n=1000

Test #12:

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

input:

4 6
4 3
1 3
2 3
4 2
4 1
2 1
2 3
4 1
4 2
4 3
2 1
1 3

output:

0

result:

ok n=4

Test #13:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4 5
2 4
4 1
4 3
2 1
3 1
2 4
2 1
4 3
4 1
3 1

output:

0

result:

ok n=4

Test #14:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

10 21
2 10
8 4
4 9
10 4
6 10
8 9
3 5
7 9
10 5
2 1
2 8
3 10
6 1
10 7
6 7
4 1
3 4
5 1
8 1
2 5
5 7
3 4
3 9
5 8
2 4
2 5
3 1
10 1
3 5
6 1
6 2
3 6
6 8
3 10
2 9
2 8
3 7
6 7
5 7
2 10
5 4
10 5

output:

-1

result:

ok n=10

Test #15:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

10 3
2 8
2 10
2 9
2 5
2 6
2 7

output:

-1

result:

ok n=10

Test #16:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10 33
2 4
2 6
8 1
5 1
7 1
6 1
6 10
3 6
8 2
3 4
5 10
8 9
7 10
2 10
4 1
3 8
4 10
1 9
4 9
8 10
6 4
2 7
1 10
10 9
2 9
2 1
8 4
6 7
4 7
7 9
5 9
6 9
5 6
4 10
1 9
5 2
6 4
2 1
5 7
7 10
2 7
5 10
8 9
6 9
10 9
7 1
3 6
4 1
2 10
7 9
8 2
2 9
3 2
2 4
6 7
1 10
5 8
4 7
3 9
6 10
3 10
8 10
8 4
6 1
8 6
4 9

output:

-1

result:

ok n=10

Test #17:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

100 149
97 53
14 62
97 60
14 58
85 69
14 63
97 99
14 71
97 88
85 47
14 61
14 43
97 44
97 17
14 39
85 17
20 99
97 73
85 31
85 67
85 12
14 24
14 69
14 96
97 76
97 95
97 11
85 79
85 19
85 70
85 6
14 56
14 12
85 98
85 53
85 76
85 26
20 37
97 35
97 70
20 96
97 82
97 34
85 94
14 46
97 54
97 43
97 4
85 2
8...

output:

-1

result:

ok n=100

Test #18:

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

input:

100 4631
2 12
66 70
81 62
5 66
94 2
92 64
62 96
58 39
34 3
21 96
52 15
23 67
62 29
38 18
72 56
67 50
81 70
38 42
81 68
99 22
61 42
30 71
32 93
46 95
27 72
97 37
27 2
46 73
65 2
94 22
33 11
64 73
44 5
48 13
65 16
24 44
61 15
34 71
40 1
60 87
100 66
84 33
81 7
14 69
57 83
63 79
23 96
34 15
72 41
47 12...

output:

-1

result:

ok n=100

Test #19:

score: 0
Accepted
time: 37ms
memory: 4000kb

input:

1000 261943
229 141
480 681
189 131
575 202
700 642
405 254
845 739
920 506
838 6
366 32
886 326
124 749
375 702
426 316
843 800
736 845
752 171
744 236
169 313
612 804
675 808
230 804
454 695
617 445
606 481
766 254
140 421
483 155
775 115
617 583
710 417
936 649
329 53
526 979
833 382
464 327
475 ...

output:

-1

result:

ok n=1000

Test #20:

score: 0
Accepted
time: 5ms
memory: 3900kb

input:

1000 48821
306 916
554 937
602 467
778 306
291 993
446 28
561 538
566 718
833 139
857 553
738 128
153 811
350 290
458 146
211 897
158 828
925 574
291 91
530 933
833 387
773 926
554 776
900 41
158 186
877 717
975 113
360 451
375 101
980 364
96 203
492 953
29 280
469 540
153 604
44 911
601 229
469 858...

output:

-1

result:

ok n=1000

Test #21:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

4 1
4 1
4 1

output:

0

result:

ok n=4

Test #22:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

6 5
6 3
5 6
2 6
2 3
6 4
6 5
6 4
6 2
2 3
6 3

output:

0

result:

ok n=6

Test #23:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

6 1
3 1
1 2

output:

-1

result:

ok n=6

Test #24:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10 34
7 2
8 10
10 9
6 1
6 5
2 4
6 4
2 5
7 4
2 3
9 4
1 5
6 3
2 1
3 4
4 5
3 5
8 4
7 6
8 1
6 9
10 5
10 4
7 9
3 9
2 9
3 1
1 4
10 6
8 2
8 7
6 2
9 5
1 9
6 2
4 9
4 2
7 8
2 10
4 10
4 8
4 1
2 1
4 7
6 9
6 1
5 8
4 6
1 3
9 7
6 3
9 10
2 5
4 5
6 8
9 5
5 7
2 3
1 10
2 9
4 3
2 8
3 10
1 5
9 1
6 7
6 5
9 3

output:

5
1 8 10 5
2 7 10 1
5 6 7 8
7 1 8 10
3 5 10 6

result:

ok n=10

Test #25:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

10 27
10 2
6 4
5 2
5 4
2 7
10 5
1 6
1 9
5 7
3 2
6 9
6 2
8 1
3 7
3 6
8 3
7 9
5 9
5 6
2 9
4 7
6 7
2 4
3 9
10 1
4 9
8 7
6 3
9 4
6 1
2 3
1 10
6 4
2 1
1 8
6 9
3 4
7 5
2 5
5 8
9 8
2 7
6 2
2 9
6 5
7 3
7 10
9 3
9 5
7 4
2 4
6 7
7 9
5 10

output:

5
1 9 2 10
3 8 4 2
4 5 2 1
5 1 8 2
7 8 10 9

result:

ok n=10

Test #26:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

10 12
8 9
8 1
9 3
9 1
9 4
9 5
9 2
9 10
8 7
3 7
9 7
8 6
9 3
7 4
9 8
7 8
9 5
7 3
9 4
7 1
9 1
9 6
9 10
9 7

output:

-1

result:

ok n=10

Test #27:

score: -100
Wrong Answer
time: 1ms
memory: 3664kb

input:

50 952
2 38
10 5
32 33
42 32
40 2
31 33
4 41
47 20
42 13
50 20
1 9
32 41
36 5
11 30
15 23
3 27
17 23
11 25
41 7
31 48
2 9
30 48
35 28
44 36
49 32
45 40
18 45
40 39
47 38
11 39
3 22
6 30
39 46
40 27
15 4
19 13
20 4
21 17
47 7
13 12
44 38
35 15
5 9
44 41
31 14
6 40
50 48
21 49
16 1
44 15
30 5
20 16
41...

output:

185
1 34 44 2
1 8 26 3
2 18 35 26
2 11 28 15
2 10 26 4
3 28 44 5
3 15 35 10
3 11 26 2
3 8 6 1
4 15 35 3
4 8 26 3
5 37 45 2
5 34 15 6
5 28 11 6
5 20 8 28
6 48 47 8
6 43 44 10
6 38 39 8
6 34 36 1
6 33 29 10
6 31 15 18
6 28 11 5
6 18 10 9
6 16 8 34
6 14 7 11
6 12 1 8
7 36 45 11
7 28 34 3
7 26 11 2
8 49...

result:

wrong answer Wrong Answer!
English 繁體中文 简体中文

服务器时间: 2024-12-02 13:50:17 | 开源项目