Submission #1042068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042068		ProtonDecay314	Parachute rings (IOI12_rings)	C++17	100 / 100	1520 ms	126248 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;
vector<UF> ufs;

int ans;
vi crit;
vvi degs;

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 create_ufs_and_degs() {
    ufs.clear();
    int ind = 0;
    for(int i : crit) {
        ufs.pb({N});
        vi degr(N, 0);
        degs.pb(degr);

        for(int i1 = 0; i1 < N; i1++) {
            if(i1 == i) continue;
            for(int i2 : adj[i1]) {
                if(i2 == i) continue;
                ufs.back().unify(i1, i2);
            }
        }

        for(int i1 = 0; i1 < N; i1++) {
            for(int j : adj[i1]) {
                if(j == i) continue;
                degs[ind][i1]++;
            }
        }
        ind++;
    }
}

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 = 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.pb(three_node);
            for(int i : adj[three_node]) {
                if(is_crit(i)) crit.pb(i);
            }

            ans = crit.size();

            create_ufs_and_degs();
        }
    } else {
        vi to_remove;

        for(int i = 0; i < ans; i++) {
            if(A == crit[i] || B == crit[i]) continue;
            degs[i][A]++;
            degs[i][B]++;
            bool made_three = degs[i][A] == 3 || degs[i][B] == 3;
            if(ufs[i].conn(A, B) || made_three) {
                to_remove.pb(i);
            }
            ufs[i].unify(A, B);
        }

        for(int i = to_remove.size() - 1; i >= 0; i--) {
            // cout << to_remove[i] << " ";
            crit.erase(next(crit.begin(), to_remove[i]));
            ufs.erase(next(ufs.begin(), to_remove[i]));
            degs.erase(next(degs.begin(), to_remove[i]));
        }
        // cout << endl;

        ans = crit.size();
    }

    // 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;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:201:10: warning: unused variable 'cycle_made' [-Wunused-variable]
  201 |     bool cycle_made = uf->conn(A, B);
      |          ^~~~~~~~~~

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