QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #629255 | #4635. Graph Operation | lwm7708 | WA | 0ms | 3552kb | C++17 | 8.6kb | 2024-10-11 09:52:15 | 2024-10-11 09:52:15 |
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]) >> (i + 1) << (i + 1);
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]) >> (i + 1) << (i + 1);
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: 3548kb
input:
4 2 1 2 3 4 1 3 2 4
output:
1 1 2 3 4
result:
ok n=4
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3552kb
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:
4 1 2 3 2 2 2 4 3 3 5 4 5 4 6 5 5
result:
wrong answer Vertices must be distinct!