oj.uz

Submission #411443

# Submission time Handle Problem Language Result Execution time Memory
411443 2021-05-25T10:57:44 Z KoD Parachute rings (IOI12_rings) C++17
0 / 100
 4000 ms 144176 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct UnionFind {
    Vec<int> par;
    UnionFind() = default;
    UnionFind(const int size): par(size, -1) { }
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    int size(const int u) {
        return -par[find(u)];
    }
    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return false;
        if (par[u] > par[v]) {
            std::swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

struct StateManager {
    UnionFind dsu;
    Vec<int> deg;
    int bad;
    bool ok;
    StateManager() = default;
    StateManager(const int size, const int bad): dsu(size), deg(size), bad(bad), ok(true) { }
    void add_edge(const int u, const int v) {
        if (u == bad or v == bad) return;
        deg[u] += 1;
        deg[v] += 1;
        if (!dsu.merge(u, v) or deg[u] >= 3 or deg[v] >= 3) {
            ok = false;
        }
    }
};

int N;
Vec<Vec<int>> adj;
Vec<std::pair<int, int>> history;
UnionFind dsu;
Vec<bool> processed;
Vec<StateManager> whatif;
Vec<std::set<int>> deglist;


/*
0: no deg >= 3, no cycles
1: no deg >= 3, one cycle
2: some deg == 3
3: one deg >= 4
-1: bad, always CountCritical() == 0
*/

int state;
int cycle_leader;

void Init(int N_) {
    N = N_;
    adj.resize(N);
    dsu = UnionFind(N);
    processed = Vec<bool>(N);
    deglist = Vec<std::set<int>>(N + 5);
    for (int i = 0; i < N; ++i) {
        deglist[0].insert(i);
    }
}

void Link(int A, int B) {
    if (state == -1) return;
    deglist[adj[A].size()].erase(A);
    deglist[adj[B].size()].erase(B);
    adj[A].push_back(B);
    adj[B].push_back(A);
    deglist[adj[A].size()].insert(A);
    deglist[adj[B].size()].insert(B);
    if (deglist[4].size() >= 2) {
        state = -1;
        return;
    }
    if (!deglist[4].empty()) {
        if (state != 3) {
            state = 3;
            const auto u = *deglist[4].begin();
            whatif.clear();
            whatif.emplace_back(N, u);
            for (const auto [x, y]: history) {
                whatif[0].add_edge(x, y);
            }
        }
        whatif[0].add_edge(A, B);
    }
    else {
        if (deglist[3].size() >= 4) {
            state = -1;
            return;
        }
        if (!deglist[3].empty()) {
            state = 2;
            for (const auto u: deglist[3]) {
                if (!processed[u]) {
                    processed[u] = true;
                    whatif.emplace_back(N, u);
                    for (const auto [x, y]: history) {
                        whatif.back().add_edge(x, y);
                    }
                }
            }
            for (const auto v: deglist[3]) {
                for (const auto u: adj[v]) {
                    if (!processed[u]) {
                        processed[u] = true;
                        whatif.emplace_back(N, u);
                        for (const auto [x, y]: history) {
                            whatif.back().add_edge(x, y);
                        }
                    }
                }
            }
            for (auto& state: whatif) {
                state.add_edge(A, B);
            }
        }
        else {
            if (!dsu.merge(A, B)) {
                if (cycle_leader != -1) {
                    state = -1;
                    return;
                }
                state = 1;
                cycle_leader = dsu.find(A);
            }
        }
    }
    history.emplace_back(A, B);
}

int CountCritical() {
    if (state == 0) {
        return N;
    }
    if (state == 1) {
        return dsu.size(cycle_leader);
    }
    if (state == 2 or state == 3) {
        int ret = 0;
        for (const auto& state: whatif) {
            if (state.ok) {
                ret += 1;
            }
        }
        return ret;
    }
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2233 ms 90752 KB Output is correct
2 Execution timed out 4075 ms 144176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1132 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Incorrect 2 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -