Submission #1041107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041107		ProtonDecay314	Parachute rings (IOI12_rings)	C++17	0 / 100	4086 ms	33112 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;
bool is_zero = false;
int three_node = -1;
int four_node = -1;

vvi adj;
UF *uf;

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

    int num_1s = 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++;
    }

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

    int cid = 0;
    for(int s = 0; s < N; s++) {
        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 (cid << 1) == num_1s;
}

void Init(int N_) {
    N = N_;
    uf = new UF(N);
    for(int i = 0; i < N; i++) {
        vi adjr;
        adj.pb(adjr);
    }
    // Yeah nope, I preallocated my union find haha
}

void Link(int A, int B) {
    // if(is_zero) 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);
    //     }
    // }
    // if(comps_with_cycle.size() == 2) {
    //     is_zero = true;
    //     return;
    // }

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

    // Check comp sizes
    // if(three_node == -1) {
    //     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
    // }

    // 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() {
    // if(is_zero) return 0;

    int count = 0;

    for(int i = 0; i < N; i++) {
        if(is_crit(i)) count++;
    }

    return count;;
}

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