Submission #551275

#	Time	Username	Problem	Language	Result	Execution time	Memory
551275		elazarkoren	Parachute rings (IOI12_rings)	C++17	52 / 100	4078 ms	234884 KiB

rings

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;

struct Dsu {
    vi par, sz, deg;
    vector<multiset<pii, greater<pii>>> degs;
    set<int> bad_comps;
    int erased_node;
    bool good = true;
    Dsu() {}
    Dsu(int n, int node): erased_node(node) {
        par.resize(n), sz.resize(n), deg.resize(n);
        degs.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i, sz[i] = 1;
            degs[i].insert({0, i});
        }
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) {
            bad_comps.insert(pa);
            good = false;
            return;
        }
        if (sz[pa] < sz[pb]) swap(pa, pb);
        if (bad_comps.count(pb)) {
            bad_comps.erase(bad_comps.find(pb));
            bad_comps.insert(pa);
            good = false;
        }
        sz[pa] += sz[pb];
        par[pb] = pa;
        for (pii p : degs[pb]) {
            degs[pa].insert(p);
        }
        degs[pb].clear();
    }
    void Add(int a, int b) {
        if (a == erased_node || b == erased_node) return;
        Union(a, b);
        int pa = Find(a);
        degs[pa].erase(degs[pa].find({deg[a], a}));
        degs[pa].erase(degs[pa].find({deg[b], b}));
        deg[a]++, deg[b]++;
        degs[pa].insert({deg[a], a});
        degs[pa].insert({deg[b], b});
        if (deg[a] > 2 || deg[b] > 2) {
            bad_comps.insert(pa);
            good = false;
        }
    }
};

int n;

Dsu d1;
bool changed = false;

vi graph[MAX_N];

void Init(int N_) {
    n = N_;
    d1 = Dsu(n, -1);
}

vector<Dsu> dsu;
vii edges;

void Link(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
    edges.push_back({a, b});
    if (!changed) {
        d1.Add(a, b);
    } else {
        for (auto &d : dsu) {
            d.Add(a, b);
        }
    }
}

int CountCritical() {
    if (changed) {
        int cnt = 0;
        for (auto &d : dsu) cnt += d.good;
        return cnt;
    }
    if (d1.good) return n;
    if (d1.bad_comps.size() == 1) {
        int node = *d1.bad_comps.begin();
        auto [max_deg, v] = *d1.degs[node].begin();
        if (max_deg == 2) return d1.sz[node];
        changed = true;
        int cnt = 0;
        dsu.push_back(Dsu(n, v));
        if (max_deg <= 3) {
            for (int neighbor : graph[v]) {
                dsu.push_back(Dsu(n, neighbor));
            }
        }
        for (auto &d : dsu) {
            for (pii p : edges) {
                d.Add(p.x, p.y);
            }
        }
        return CountCritical();
    }
    changed = true;
    return 0;
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:110:13: warning: unused variable 'cnt' [-Wunused-variable]
  110 |         int cnt = 0;
      |             ^~~

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