oj.uz

답안 #411467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411467 2021-05-25T11:25:03 Z KoD 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 4000 ms 139980 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 or !ok) 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 = -1;

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() >= 5) {
            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
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1100 KB Output is correct
3 Correct 7 ms 1100 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 5 ms 996 KB Output is correct
9 Correct 9 ms 1372 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2266 ms 83920 KB Output is correct
2 Execution timed out 4099 ms 139980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1100 KB Output is correct
3 Correct 7 ms 1100 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 5 ms 996 KB Output is correct
9 Correct 9 ms 1372 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 8 ms 1356 KB Output is correct
12 Correct 19 ms 2804 KB Output is correct
13 Correct 15 ms 2460 KB Output is correct
14 Incorrect 6 ms 2636 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1100 KB Output is correct
3 Correct 7 ms 1100 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 5 ms 996 KB Output is correct
9 Correct 9 ms 1372 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 8 ms 1356 KB Output is correct
12 Correct 19 ms 2804 KB Output is correct
13 Correct 15 ms 2460 KB Output is correct
14 Incorrect 6 ms 2636 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 1100 KB Output is correct
3 Correct 7 ms 1100 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 5 ms 996 KB Output is correct
9 Correct 9 ms 1372 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 2266 ms 83920 KB Output is correct
12 Execution timed out 4099 ms 139980 KB Time limit exceeded
13 Halted 0 ms 0 KB -