Submission #1041451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041451		ProtonDecay314	Parachute rings (IOI12_rings)	C++17	37 / 100	1559 ms	62892 KiB

rings

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

class UF {
    public:
        vi par;
        vi csize;
        int n;
        int ncomps;

        UF(int a_n): par(a_n, 0), csize(a_n, 1), n(a_n), ncomps(a_n) {
            for(int i = 0; i < n; i++) {
                par[i] = i;
            }
        }

        int find(int i) {
            while(i != par[i]) {
                par[i] = par[par[i]];
                i = par[i];
            }

            return i;
        }

        int conn(int i, int j) {
            return find(i) == find(j);
        }

        void unify(int i, int j) {
            int pari = find(i), parj = find(j);
            if(pari == parj) return;

            if(csize[pari] < csize[parj]) {
                par[pari] = parj;
                csize[parj] += csize[pari];
            } else {
                par[parj] = pari;
                csize[pari] += csize[parj];
            }

            ncomps--;
        }
};

int N;

vector<int> comps_with_cycle;
bool found_two_cycles = false;
int three_node = -1;

vvi adj;
UF *uf;

int ans;
set<int> crit;
set<int> neighborhoud_crit;

bool is_crit(int cur_n) {
    vb conn(N, false);
    for(int j: adj[cur_n]) {
        conn[j] = true;
    }

    int num_1s = 0;
    int num_0s = 0;
    for(int i = 0; i < N; i++) {
        if(i == cur_n) continue;
        int sz = adj[i].size();
        if(conn[i]) {
            sz--;
        }
        if(sz >= 3) return false;
        if(sz == 1) num_1s++;
        if(sz == 0) num_0s++;
    }

    // ! DFS could be optimized
    stack<int> st;
    vb vis(N, false);

    int cid = 0;
    for(int s = 0; s < N; s++) {
        if(s == cur_n) {
            continue;
        }
        if(!vis[s]) {
            st.push(s);

            while(!st.empty()) {
                int i = st.top();
                st.pop();
                if(vis[i]) continue;
                vis[i] = true;

                for(int j : adj[i]) {
                    if(j == cur_n) continue;
                    st.push(j);
                }
            }
            cid++;
        }
    }

    return ((num_1s & 0b1) == 0 && (num_1s >> 1) + num_0s == cid);
}

void upd_neighborhood() {
    neighborhoud_crit.clear();
    for(int i : crit) {
        neighborhoud_crit.insert(i);

        for(int j : adj[i]) {
            neighborhoud_crit.insert(j);
        }
    }
}

void Init(int N_) {
    N = N_;
    ans = N;
    uf = new UF(N);
    for(int i = 0; i < N; i++) {
        vi adjr;
        adj.pb(adjr);
    }
}

void Link(int A, int B) {
    if(ans == 0) return; // refuse to even process haha
    
    int ncyclecomps = comps_with_cycle.size();
    if(ncyclecomps < 2) {
        if(ncyclecomps > 0) {
            comps_with_cycle[0] = uf->find(comps_with_cycle[0]);
        }
        if(uf->conn(A, B)) {
            // Possible cycle
            int poss_cycle_comp = uf->find(A);

            if(ncyclecomps == 0 || poss_cycle_comp != comps_with_cycle[0]) comps_with_cycle.pb(poss_cycle_comp);
        }
    }
    ncyclecomps = comps_with_cycle.size();
    if(comps_with_cycle.size() == 2) {
        ans = 0;
        return;
    }

    bool cycle_made = uf->conn(A, B);

    uf->unify(A, B);
    adj[A].pb(B);
    adj[B].pb(A);

    // Check comp sizes
    if(three_node == -1) {
        if(ncyclecomps == 1) {
            ans = min(ans, uf->csize[uf->find(comps_with_cycle[0])]);
        }
        if(adj[A].size() == 3) three_node = A;
        if(adj[B].size() == 3) three_node = B;

        // If you find a "three" node, immediately reprocess the graph
        // As in, check which ones of the neighbors of the three node are crit
        if(three_node != -1) {
            if(is_crit(three_node)) crit.insert(three_node);
            for(int i : adj[three_node]) {
                if(is_crit(i)) crit.insert(i);
            }

            upd_neighborhood();
            ans = crit.size();
        }
    } else {
        // Check if the updated node is incident to the "neighborhood" of the nodes
        // or if it creates a new loop outside the neighborhood
        // By amortization, this should be O(1) amortized time

        if(neighborhoud_crit.count(A) > 0 || neighborhoud_crit.count(B) > 0) {
            bool changed = false;
            vi to_remove;
            for(int i : crit) {
                if(!is_crit(i)) {
                    to_remove.pb(i);
                    changed = true;
                }
            }

            for(int i : to_remove) crit.erase(i);

            if(changed) {
                upd_neighborhood();
            }

            if(crit.size() == 0) {
                ans = 0;
                return;
            }

            ans = crit.size();
        } else if (cycle_made) {
            ans = 0;
        }
    }

    // To simplify casework, idt we need the "four_node" thingy
    // if(four_node == -1) {
    //     if(adj[A].size() == 4) four_node = A;
    //     if(adj[B].size() == 4) four_node = B;
        
    //     // If you find a "four" node, immediately reprocess the graph
    // }
}

int CountCritical() {
    return ans;
}

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