Submission #520362

#	Time	Username	Problem	Language	Result	Execution time	Memory
520362		Cyanmond	Parachute rings (IOI12_rings)	C++17	0 / 100	807 ms	78020 KiB

rings

#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 h) {
                    cyclet = true;
                } else {
                    impossible = true;
                }
            }
        }
    }
}

int count_critical() {
    if (not started) {
        return N;
    }
    if (impossible) {
        return 0;
    }
    return count();
}

void Init(int n) {
    init(n);
}

void Link(int A, int B) {
    link(A, B);
}

int CountCritical() {
    return count_critical();
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31