QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #629247 | #4635. Graph Operation | lwm7708 | WA | 72ms | 4204kb | C++17 | 8.6kb | 2024-10-11 09:46:20 | 2024-10-11 09:46:20 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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!