Submission #999979

#	Time	Username	Problem	Language	Result	Execution time	Memory
999979		shmax	Parachute rings (IOI12_rings)	C++17	37 / 100	965 ms	89696 KiB

rings

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
using namespace __gnu_pbds;
#define len(x) (int) x.size()


template<typename T>
using graph = vector<vector<T>>;


template<typename T>
using vec = vector<T>;


struct DSU {
public:
    DSU() : _n(0) {}

    explicit DSU(int n) : _n(n), parent_or_size(n, -1) {}

    int unite(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool one(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
                std::remove_if(result.begin(), result.end(),
                               [&](const std::vector<int> &v) { return v.empty(); }),
                result.end());
        return result;
    }

private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

int n;
graph<int> g;
DSU dsu;
bool is_zero = false;
vec<int> deg;
//set<pair<int, int>> deg_sorted;
int rootb3 = -1;
int cnt3 = 0;
vec<int> roots3;
vec<bool> goods3;
vec<int> neight3;
vec<int> goodneight3;
vec<DSU> dsues;
vec<DSU> neightdsues;
vec<bool> have3;
vec<bool> have;
DSU dsu2;
int cycle_sz;
int cnt_cyc = 0;
int mx1 = 0;
int mx2 = 0;
int mx1id = -1;

void Init(int32_t N_) {
    n = N_;
    have.resize(n, false);
    //    dsu = DSU(n);
    g.resize(n);
    deg.resize(n);
    have3.resize(n);
    for (int i = 0; i < n; i++) {
    }
    dsu2 = DSU(n);
}

pair<bool, DSU> create(int v) {
    DSU d = DSU(n);
    for (int i = 0; i < n; i++) {
        if (i == v) continue;
        for (auto &j: g[i]) {
            if (j == v) continue;
            if (i < j) continue;
            if (d.one(i, j)) {
                return {false, d};
            }
            d.unite(i, j);
        }
    }
    return {true, d};
}

bool add(DSU &d, int a, int b, int v) {
    if (a == v or b == v) return true;
    if (d.one(a, b)) return false;
    d.unite(a, b);
    return true;
}


void Link(int32_t a, int32_t b) {
    if (is_zero)return;
    if (rootb3 != -1) {
        if (!add(dsu, a, b, rootb3)) {
            is_zero = true;
            return;
        }
    } else {
        for (int i = 0; i < len(roots3); i++) {
            if (!goods3[i]) continue;
            goods3[i] = add(dsues[i], a, b, roots3[i]);
        }
        if (cnt3 < 3)
            for (int i = 0; i < len(neight3); i++) {
                if (!goodneight3[i]) continue;
                goodneight3[i] = add(neightdsues[i], a, b, neight3[i]);
            }
    }
    g[a].push_back(b);
    g[b].push_back(a);
    deg[a]++;
    deg[b]++;
    if (mx1 < deg[a]) {
        if (mx1id != a)
            mx2 = mx1;
        mx1 = deg[a];
        mx1id = a;
    } else if (mx2 < deg[a]) {
        mx2 = deg[a];
    }
    if (mx1 < deg[b]) {
        if (mx1id != b)
            mx2 = mx1;
        mx1 = deg[b];
        mx1id = b;
    } else if (mx2 < deg[b]) {
        mx2 = deg[b];
    }
    if (mx2 > 3 - (rootb3 != -1)) {
        is_zero = true;
        return;
    }
    if (rootb3 == -1 and mx1 > 3) {
        rootb3 = mx1id;
        for (auto &i: g[rootb3]) {
            deg[i]--;
        }
        mx1 = 0;
        mx2 = 0;
        mx1id = -1;
        for (int i = 0; i < n; i++) {
            if (deg[i] > mx1) {
                mx1 = deg[i];
                mx1id = i;
            } else if (mx2 < deg[i]) {
                mx2 = deg[i];
            }
        }
        auto [f, d] = create(rootb3);
        dsu = d;
        if (!f) {
            is_zero = true;
            return;
        }
    }
    if (rootb3 == -1) {
        if (deg[a] == 3) {
            {
                cnt3++;
                roots3.push_back(a);
                auto [f, d] = create(a);
                dsues.push_back(d);
                goods3.push_back(f);
            }
        }
        auto check = [&](int v) {
            int t = 0;
            for (auto u: g[v])
                t += (deg[u] == 3);
            return t + (deg[v] == 3) == cnt3;
        };
        if (deg[b] == 3) {
            {
                cnt3++;
                roots3.push_back(b);
                auto [f, d] = create(b);
                dsues.push_back(d);
                goods3.push_back(f);
            }
            if (cnt3 < 3) {
                for (auto x: g[b]) {
                    if (have3[x] or deg[x] == 3) continue;
                    if (!check(x)) continue;
                    have3[x] = true;
                    neight3.push_back(x);
                    auto [f, d] = create(x);
                    neightdsues.push_back(d);
                    goodneight3.push_back(f);
                }
            }
        }
        if (deg[a] == 3) {
            if (cnt3 < 3) {
                for (auto x: g[a]) {
                    if (have3[x] or deg[x] == 3) continue;
                    if (!check(x)) continue;
                    have3[x] = true;
                    neight3.push_back(x);
                    auto [f, d] = create(x);
                    neightdsues.push_back(d);
                    goodneight3.push_back(f);
                }
            }
        }
        if (cnt3 > 4) {
            is_zero = true;
            return;
        }

    }
    if (roots3.empty() and rootb3 == -1) {
        if (dsu2.one(a, b)) {
            cnt_cyc++;
            cycle_sz = dsu2.size(a);
        } else {
            dsu2.unite(a, b);
        }
        if (cnt_cyc > 1) {
            is_zero = true;
        }
    }
}


int32_t CountCritical() {
    if (is_zero) return 0;
    if (n == 1) return 1;
    if (rootb3 != -1) {
        return 1;
    }
    if (!roots3.empty()) {
        auto check = [&](int v) {
            int t = 0;
            for (auto u: g[v])
                t += (deg[u] == 3);
            return t + (deg[v] == 3) == cnt3;
        };
        vec<int> can;
        for (int i = 0; i < len(roots3); i++) {
            if (!goods3[i]) continue;
            if (have[roots3[i]]) continue;
            if (!check(roots3[i])) continue;
            have[roots3[i]] = true;
            can.push_back(roots3[i]);
        }
        if (cnt3 < 3)
            for (int i = 0; i < len(neight3); i++) {
                if (!goodneight3[i]) continue;
                if (have[neight3[i]]) continue;
                if (!check(neight3[i])) continue;
                have[roots3[i]] = true;
                can.push_back(neight3[i]);
            }
        for (auto &i: can) {
            have[i] = false;
        }
        return len(can);
    }
    if (cnt_cyc == 1)
        return cycle_sz;
    if (cnt_cyc == 0)
        return n;
}

Compilation message (stderr)

rings.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
rings.cpp: In function 'int32_t CountCritical()':
rings.cpp:314:1: warning: control reaches end of non-void function [-Wreturn-type]
  314 | }
      | ^

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