#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 7 "library2/graph/union_find.hpp"
class UnionFind {
int components;
std::vector<int> data;
public:
explicit UnionFind() : components(0), data(0) {}
explicit UnionFind(const int n) : components(n), data(n, -1) {}
int size() const {
return len(data);
}
int count_components() const {
return components;
}
int find(int v) {
assert(0 <= v and v < size());
if (data[v] < 0) {
return v;
} else {
return data[v] = find(data[v]);
}
}
int size(const int v) {
return -data[find(v)];
}
bool is_same(const int a, const int b) {
return find(a) == find(b);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return false;
}
if (size(a) < size(b)) {
std::swap(a, b);
}
data[a] += data[b];
data[b] = a;
return true;
}
std::vector<std::vector<int>> decompose() {
std::vector<std::vector<int>> ret(size());
for (int i = 0; i < size(); ++i) {
ret[find(i)].push_back(i);
}
ret.erase(std::remove_if(ret.begin(), ret.end(),
[&](const std::vector<int> &v) { return v.empty(); }),
ret.end());
return ret;
}
};
#line 3 "library2/utility/int_alias.hpp"
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/scan.hpp"
template <typename T = int> T scan() {
T ret;
std::cin >> ret;
return ret;
}
#line 8 "paper.cpp"
int N;
bool impossible;
bool cyclet;
bool started;
bool fn;
UnionFind uft;
struct Edge {
int u;
int v;
};
std::vector<Edge> edges;
std::vector<std::vector<int>> graph;
int a, b, c, d;
UnionFind ufta, uftb, uftc, uftd;
bool oka, okb, okc, okd;
void add_edge(const int u, const int v) {
if (not started) {
return;
}
if (oka and a != u and a != v) {
if (not ufta.unite(u, v)) {
oka = false;
}
}
if (okb and b != u and b != v) {
if (not uftb.unite(u, v)) {
okb = false;
}
}
if (okc and c != u and c != v) {
if (not uftc.unite(u, v)) {
okc = false;
}
}
if (okd and d != u and d != v) {
if (not uftd.unite(u, v)) {
okd = false;
}
}
}
void set(const int x, const int y, const int z, const int p) {
a = x;
b = y;
c = z;
d = p;
oka = okb = okc = okd = true;
ufta = uftb = uftc = uftd = UnionFind(N);
for (const auto &[u, v] : edges) {
add_edge(u, v);
}
}
int count() {
return (oka ? 1 : 0) + (okb ? 1 : 0) + (okc ? 1 : 0) + (okd ? 1 : 0);
}
void init(const int n) {
N = n;
impossible = false;
cyclet = false;
started = false;
fn = false;
uft = UnionFind(N);
graph.resize(n);
}
int degree(const int v) {
return len(graph[v]);
}
void start(const int n) {
started = true;
set(n, graph[n][0], graph[n][1], graph[n][2]);
}
void add_degree3(const int n) {
auto is_ok = [&](const int v) {
return (v == n) or (std::find(graph[n].begin(), graph[n].end(), v) != graph[n].end());
};
if (not is_ok(a)) {
oka = false;
}
if (not is_ok(b)) {
okb = false;
}
if (not is_ok(c)) {
okc = false;
}
if (not is_ok(d)) {
okd = false;
}
}
void last_spart(const int n) {
fn = true;
if (n != a) {
oka = false;
}
if (n != b) {
okb = false;
}
if (n != c) {
okc = false;
}
if (n != d) {
okd = false;
}
}
void link(const int u, const int v) {
if (not impossible) {
add_edge(u, v);
const auto h = uft.unite(u, v);
graph[u].push_back(v);
graph[v].push_back(u);
edges.push_back({u, v});
const int da = degree(u), db = degree(v);
if (da == 3) {
if (not started) {
start(u);
} else {
add_degree3(u);
}
}
if (db == 3) {
if (not started) {
start(v);
} else {
add_degree3(v);
}
}
if (da == 4) {
last_spart(u);
}
if (db == 4) {
last_spart(v);
}
if (not started) {
if (not h) {
if (not cyclet) {
cyclet = true;
} else {
impossible = true;
}
}
}
}
}
int count_critical() {
if (impossible) {
return 0;
}
if (not started) {
return N;
}
return count();
}
void Init(int n) {
init(n);
}
void Link(int A, int B) {
link(A, B);
}
int CountCritical() {
return count_critical();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
716 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
270 ms |
34872 KB |
Output is correct |
| 2 |
Correct |
773 ms |
65968 KB |
Output is correct |
| 3 |
Correct |
774 ms |
77884 KB |
Output is correct |
| 4 |
Incorrect |
763 ms |
66820 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
716 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
716 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
716 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
