oj.uz

Submission #1041451

# Submission time Handle Problem Language Result Execution time Memory
1041451 2024-08-02T04:06:23 Z ProtonDecay314 Parachute rings (IOI12_rings) C++17
37 / 100
 1559 ms 62892 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 796 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 796 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 796 KB Output is correct
10 Correct 2 ms 796 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 32944 KB Output is correct
2 Correct 1559 ms 52136 KB Output is correct
3 Correct 138 ms 33472 KB Output is correct
4 Correct 421 ms 62892 KB Output is correct
5 Correct 419 ms 62888 KB Output is correct
6 Correct 396 ms 61608 KB Output is correct
7 Correct 264 ms 50596 KB Output is correct
8 Correct 1473 ms 60076 KB Output is correct
9 Correct 1074 ms 62892 KB Output is correct
10 Correct 298 ms 61400 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 796 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 796 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 796 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Incorrect 2 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 796 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 796 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 796 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Incorrect 2 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 796 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 2 ms 796 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 796 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Correct 172 ms 32944 KB Output is correct
12 Correct 1559 ms 52136 KB Output is correct
13 Correct 138 ms 33472 KB Output is correct
14 Correct 421 ms 62892 KB Output is correct
15 Correct 419 ms 62888 KB Output is correct
16 Correct 396 ms 61608 KB Output is correct
17 Correct 264 ms 50596 KB Output is correct
18 Correct 1473 ms 60076 KB Output is correct
19 Correct 1074 ms 62892 KB Output is correct
20 Correct 298 ms 61400 KB Output is correct
21 Incorrect 2 ms 604 KB Output isn't correct
22 Halted 0 ms 0 KB -