Submission #1183642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183642		harvsftw	Parachute rings (IOI12_rings)	C++20	52 / 100	4089 ms	301612 KiB

rings

#include <bits/stdc++.h>
using namespace std;

#define F(i, n) for (int i = 0; i < (n); i++)
#define F_reverse(i, n) for (int i = (n - 1); i >= 0; i--)

#define N 1000000

/*
ideas

deleting a node should result in graph where max degree is 2, and no cycles

so if there are nodes with degree >= 3, the node needs to be connected to all
other instances

only 1 component can have degree 3/4

case max node with upto degree >= 4:
only one with deg >= 4 can occur (otherwise no critical), and it is the only one that can be critical
it can be connected to O(n) nodes with degree 3

case node with upto degree == 3:
at most 4 3degs can occur (otherwise no critical), (3deg connected to 3 3degs)
only possible crits are them and nodes connected to them (around 16 max?)

based from hints
1. state machine that based on max deg node from 2 -> 3 -> 4+
1. if there are <= 4 3degs, naively create multiple graphs without a specific
node, and ensure they have no cycle
2. the 5th 3deg and above: skip creating sans that node-graphs their neighbors
3. the moment the 1st 4deg is created: replace graphs with sans that node graph

case node with upto degree == 2 only:
ensure upto one cycle only
impl: everthing in the connected component is crit

can store count of connected components with cycles

*/

struct dsu_clean {
    int p[N];   // parent node
    int sz[N];  // size of component

    void init(int n) {
        F(i, n) {
            p[i] = i;
            sz[i] = 1;
        }
    }

    int find(int x) {
        if (p[x] == x) {
            return x;
        }

        int ret = find(p[x]);
        p[x] = ret;
        return ret;
    }

    bool united(int a, int b) {
        int x = find(a);
        int y = find(b);
        return x == y;
    }

    void unite(int a, int b) {
        int x = find(a);
        int y = find(b);

        if (x != y) {
            if (sz[x] < sz[y]) {
                swap(x, y);
            }

            p[y] = x;
            sz[x] += sz[y];
        }
    }
};

int n;
vector<pair<int, int>> link_list;  // not to be confused with a linked list
//struct graph_sans_specific_node;

struct graph_sans_specific_node {
    dsu_clean dsu;
    bool has_cycle_flag = false;
    int excl_node;
    graph_sans_specific_node(int excl_node) { 
        dsu.init(n); 
        this->excl_node = excl_node;
        for(auto [u, v] : link_list) {
            process_input(u, v);
        }
    };

    void process_input(int u, int v) {
        //cout << excl_node << " recv " << u << " " << v << endl;
        if(u != excl_node && v != excl_node) {
            if(dsu.united(u, v)) {
                ////cout << "has cycle" << endl;
                this->has_cycle_flag = true;
            } else {
                dsu.unite(u, v);
            }
        }
    }
};
unordered_map<int, graph_sans_specific_node> graphs_without_specific_nodes;


struct dsu_main {
    int p[N];   // parent node
    int sz[N];  // size of component

    // stats
    int components_with_3deg = 0, components_with_4plusdeg = 0, components_with_cycles = 0;
    int component_with_cycle;

    // misc params
    int num_4plus_deg[N];
    int v_4plus_deg[N]; // assumes one only
    bool has_cycle[N];

    // limit to 4
    vector<unordered_set<int>> v_3_deg;

    void init(int n) {
        F(i, n) {
            p[i] = i;
            sz[i] = 1;
        }
        v_3_deg.resize(n);
    }

    int find(int x) {
        if (p[x] == x) {
            return x;
        }

        int ret = find(p[x]);
        p[x] = ret;
        return ret;
    }

    void unite(int a, int b) {
        int x = find(a);
        int y = find(b);

        if (x != y) {
            if (sz[x] < sz[y]) {
                swap(x, y);
            }

            components_with_4plusdeg -= num_4plus_deg[x] > 0;
            components_with_4plusdeg -= num_4plus_deg[y] > 0;
            components_with_3deg -= v_3_deg[x].size() > 0;
            components_with_3deg -= v_3_deg[y].size() > 0;
            components_with_cycles -= has_cycle[x];
            components_with_cycles -= has_cycle[y];

            p[y] = x;
            sz[x] += sz[y];
            num_4plus_deg[x] += num_4plus_deg[y];
            if (num_4plus_deg[x] == 0 && num_4plus_deg[y] > 0) {  // move to x
                v_4plus_deg[x] = v_4plus_deg[y];
            }

            if(num_4plus_deg[x] > 0) {
                components_with_4plusdeg++;
            }

            for (int v : v_3_deg[y]) {
                if (v_3_deg[x].size() > 4) {
                    break;
                }

                v_3_deg[x].insert(v);
            }

            if(v_3_deg[x].size() > 0) {
                components_with_3deg++;
            }

            has_cycle[x] |= has_cycle[y];
            if(has_cycle[x]) {
                components_with_cycles++;
                component_with_cycle = x;
            }
        }
    }
} dsu;

struct vertex_info {
    bool in_cyle;
    vector<int> edge_list;
    unordered_set<int> _3deg_neighbors;

    size_t count_3deg_neighbors() { return _3deg_neighbors.size(); }
    bool is_3deg() { return edge_list.size() == 3; }
};

vector<vertex_info> info(N);

unordered_set<int> get_3deg_and_neighbors(int u) {
    unordered_set<int> nodes, vis;
    int p = dsu.find(u);
    for (auto v : dsu.v_3_deg[p]) {
        //cout << v << " has 3 edges" << endl;
        for (auto u : info[v].edge_list) {
            // if(vis.contains(u)) {
            //   continue;
            // }
            // vis.insert(u);

           nodes.insert(u);
        }
        nodes.insert(v);
    }
    return nodes;
}

void Init(int N_) {
    dsu.init(N_);
    n = N_;
}

size_t _3deg_node_cnt = 0, _4plusdeg_node_cnt = 0;

int dbg;
void Link(int A, int B) {
    link_list.emplace_back(A, B);
    for(auto& [_, g] : graphs_without_specific_nodes) { // note & is needed
        g.process_input(A, B);
    }

    int u = dsu.find(A), v = dsu.find(B);
    if(u == v && !dsu.has_cycle[u]) {
        // cycle detected
        dsu.has_cycle[u] = true;
        dsu.components_with_cycles++;
        dsu.component_with_cycle = u;
    }

    // //cout << A << ' ' << B << endl;
    info[A].edge_list.push_back(B);
    info[B].edge_list.push_back(A);
    
    auto handle_changes = [&](int u, int dsu_rep) {
        int deg = info[u].edge_list.size();
        if (deg == 3) {
            for (int v : info[u].edge_list) {
                info[v]._3deg_neighbors.insert(u);
            }
            dsu.v_3_deg[dsu_rep].insert(u);
            if(dsu.v_3_deg[dsu_rep].size() == 1) {
                dsu.components_with_3deg++;
            } 

            _3deg_node_cnt++;

            if(_4plusdeg_node_cnt == 0 && _3deg_node_cnt <= 4) {
                auto community = get_3deg_and_neighbors(u);
                for(int v : community) {
                    if(graphs_without_specific_nodes.find(v) == graphs_without_specific_nodes.end()) {
                        graphs_without_specific_nodes.emplace(v, graph_sans_specific_node(v));
                    }
                }
            }
        } else if (deg == 4) {
            for (int v : info[u].edge_list) {
                info[v]._3deg_neighbors.erase(u);
            }
            dsu.v_3_deg[dsu_rep].erase(u);
            if(dsu.num_4plus_deg[dsu_rep]++ == 0) dsu.components_with_4plusdeg++;
            dsu.v_4plus_deg[dsu_rep] = u;
            
            _3deg_node_cnt--;
            _4plusdeg_node_cnt++;

            if(_4plusdeg_node_cnt == 1) {
                graphs_without_specific_nodes.clear();
                graphs_without_specific_nodes.emplace(u, graph_sans_specific_node(u));
            }
        }
    };

    if(3 <= info[A].edge_list.size() && info[A].edge_list.size() <= 4) handle_changes(A, u);
    if(3 <= info[B].edge_list.size() && info[B].edge_list.size() <= 4) handle_changes(B, v);

    dsu.unite(A, B);
    //cout << ++dbg << endl;
    // //cout << "components with 3deg: " << components_with_3deg.size() << endl;
    // //cout << "components with 4+deg: " << components_with_4plusdeg.size() << endl;
}


int CountCritical() {
    // F(i, n) {
    //     if(dsu.p[i] == i) {
    //         cout << "found connected component of size " << dsu.sz[i] << endl;
    //     }
    // }
    // cout << dsu.components_with_4plusdeg << " " << dsu.components_with_3deg << endl;
    // cout << _3deg_node_cnt << " " << _4plusdeg_node_cnt << endl;

    if(dsu.components_with_4plusdeg > 0) {
        //cout << "case 4+\n";
        if(dsu.components_with_4plusdeg == 1 && _4plusdeg_node_cnt == 1) {
            assert(graphs_without_specific_nodes.size() == 1); // hack

            for(auto [_, graph_without_the_only_4plusdeg] : graphs_without_specific_nodes) {
                return info[graph_without_the_only_4plusdeg.excl_node].count_3deg_neighbors() == _3deg_node_cnt && !graph_without_the_only_4plusdeg.has_cycle_flag;
            }
        } else {
            return 0;
        }
    }  else if(dsu.components_with_3deg > 0) {
        //cout << "case 3\n";
        if(dsu.components_with_3deg == 1) {
            int dsu_rep = dsu.find(graphs_without_specific_nodes.begin()->second.excl_node); // hack

            auto candidates = get_3deg_and_neighbors(dsu_rep);
            int cnt = 0;
            for(int cand : candidates) {
                auto it = graphs_without_specific_nodes.find(cand);
                assert(it != graphs_without_specific_nodes.end());
                assert(it->second.excl_node == cand);

                //cout << "candidate " << cand << ": " << info[cand].count_3deg_neighbors() << " + " << info[cand].is_3deg() << " == " << _3deg_node_cnt << " with cycle: " << it->second.has_cycle_flag << endl;
                cnt += info[cand].count_3deg_neighbors() + info[cand].is_3deg() == _3deg_node_cnt && !it->second.has_cycle_flag;
            }
            return cnt;
        } else {
            return 0;
        }
    } else {
        //cout << "case 2-\n";
        if(dsu.components_with_cycles == 0) {
            return n;
        } else if(dsu.components_with_cycles == 1) {
            return dsu.sz[dsu.component_with_cycle];
        } else {
            return 0;
        }
    }

    assert(false);
}

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