oj.uz

Submission #594037

# Submission time Handle Problem Language Result Execution time Memory
594037 2022-07-12T00:13:36 Z skittles1412 Parachute rings (IOI12_rings) C++17
0 / 100
 1108 ms 91860 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 1e6 + 5;

struct DSU {
    bool cyc;
    int p[maxn];

    DSU() : cyc(false) {
        memset(p, -1, sizeof(p));
    }

    int find(int u) {
        return p[u] < 0 ? u : (p[u] = find(p[u]));
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            cyc = true;
            return;
        }
        if (p[u] < p[v]) {
            swap(u, v);
        }
        p[v] += p[u];
        p[u] = v;
    }
} dsus[4];

int n, dcnt[5], big[maxn], imp[4];
vector<int> graph[maxn];
vector<pair<int, int>> edges;

void Init(int _n) {
    n = _n;
    imp[0] = -1;
}

void upd_dcnt(int d) {
    dcnt[min(d, 4)]--;
    dcnt[min(d + 1, 4)]++;
}

void Link(int u, int v) {
    edges.emplace_back(u, v);
    upd_dcnt(sz(graph[u]));
    upd_dcnt(sz(graph[v]));
    if (sz(graph[u]) >= 3) {
        big[v]++;
    }
    if (sz(graph[v]) >= 3) {
        big[u]++;
    }
    graph[u].push_back(v);
    graph[v].push_back(u);
    if (sz(graph[u]) == 3) {
        big[u]++;
        for (auto& a : graph[u]) {
            big[a]++;
        }
    }
    if (sz(graph[v]) == 3) {
        big[v]++;
        for (auto& a : graph[v]) {
            big[a]++;
        }
    }
    if (imp[0] == -1) {
        int cx = -1;
        if (sz(graph[u]) >= 3) {
            cx = u;
        } else if (sz(graph[v]) >= 3) {
            cx = v;
        }
        if (cx != -1) {
            assert(sz(graph[cx]) == 3);
            for (int i = 0; i < 4; i++) {
                int cy;
                if (i < 3) {
                    cy = graph[cx][i];
                } else {
                    cy = cx;
                }
                imp[i] = cy;
                for (auto& [u, v] : edges) {
                    if (u != cy && v != cy) {
                        dsus[i].merge(u, v);
                    }
                }
            }
        }
    } else {
        for (int i = 0; i < 4; i++) {
            if (u != imp[i] && v != imp[i]) {
                dsus[i].merge(u, v);
            }
        }
    }
}

int CountCritical() {
    if (dcnt[4] >= 2) {
        return 0;
    } else if (imp[0] != -1) {
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            bool cur = !dsus[i].cyc;
            if (dcnt[4] == 1) {
                cur &= sz(graph[imp[i]]) >= 4;
            }
            cur &= big[imp[i]] == dcnt[3] + dcnt[4];
            ans += cur;
        }
        return ans;
    } else {
        assert(!dcnt[4] && !dcnt[3]);
        return n;
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39444 KB Output is correct
2 Correct 20 ms 39672 KB Output is correct
3 Correct 19 ms 39660 KB Output is correct
4 Incorrect 19 ms 39496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 66660 KB Output is correct
2 Correct 858 ms 81532 KB Output is correct
3 Correct 1108 ms 90716 KB Output is correct
4 Incorrect 721 ms 91860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39444 KB Output is correct
2 Correct 20 ms 39672 KB Output is correct
3 Correct 19 ms 39660 KB Output is correct
4 Incorrect 19 ms 39496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39444 KB Output is correct
2 Correct 20 ms 39672 KB Output is correct
3 Correct 19 ms 39660 KB Output is correct
4 Incorrect 19 ms 39496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39444 KB Output is correct
2 Correct 20 ms 39672 KB Output is correct
3 Correct 19 ms 39660 KB Output is correct
4 Incorrect 19 ms 39496 KB Output isn't correct
5 Halted 0 ms 0 KB -