oj.uz

Submission #1041449

# Submission time Handle Problem Language Result Execution time Memory
1041449 2024-08-02T04:04:22 Z ProtonDecay314 Parachute rings (IOI12_rings) C++17
37 / 100
 1560 ms 76224 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 = 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 1 ms 344 KB Output is correct
2 Correct 2 ms 756 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 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 32940 KB Output is correct
2 Correct 1241 ms 51420 KB Output is correct
3 Correct 140 ms 34756 KB Output is correct
4 Correct 431 ms 63904 KB Output is correct
5 Correct 447 ms 63860 KB Output is correct
6 Correct 443 ms 61828 KB Output is correct
7 Correct 273 ms 62124 KB Output is correct
8 Correct 1560 ms 71844 KB Output is correct
9 Correct 1153 ms 76224 KB Output is correct
10 Correct 293 ms 73672 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 756 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 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 756 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 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 756 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 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 142 ms 32940 KB Output is correct
12 Correct 1241 ms 51420 KB Output is correct
13 Correct 140 ms 34756 KB Output is correct
14 Correct 431 ms 63904 KB Output is correct
15 Correct 447 ms 63860 KB Output is correct
16 Correct 443 ms 61828 KB Output is correct
17 Correct 273 ms 62124 KB Output is correct
18 Correct 1560 ms 71844 KB Output is correct
19 Correct 1153 ms 76224 KB Output is correct
20 Correct 293 ms 73672 KB Output is correct
21 Incorrect 2 ms 860 KB Output isn't correct
22 Halted 0 ms 0 KB -