oj.uz

답안 #1041462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041462 2024-08-02T04:16:41 Z ProtonDecay314 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 1707 ms 71076 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, *ufsmall;

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);
    ufsmall = 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);
            }

            for(int i = 0; i < N; i++) {
                for(int j : adj[i]) {
                    if(crit.count(j) > 0) continue;
                    ufsmall->unify(i, j);
                }
            }

            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 (ufsmall->conn(A, B)) {
            ans = 0;
        }

        ufsmall->unify(A, B);
    }

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

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 760 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 796 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 688 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 796 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 36916 KB Output is correct
2 Correct 1376 ms 58284 KB Output is correct
3 Correct 142 ms 41032 KB Output is correct
4 Correct 454 ms 70824 KB Output is correct
5 Correct 468 ms 71076 KB Output is correct
6 Correct 485 ms 70564 KB Output is correct
7 Correct 361 ms 57868 KB Output is correct
8 Correct 1707 ms 68028 KB Output is correct
9 Correct 1195 ms 71076 KB Output is correct
10 Correct 279 ms 69280 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 760 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 796 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 688 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Incorrect 2 ms 856 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 760 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 796 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 688 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Incorrect 2 ms 856 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 760 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 796 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 688 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Correct 149 ms 36916 KB Output is correct
12 Correct 1376 ms 58284 KB Output is correct
13 Correct 142 ms 41032 KB Output is correct
14 Correct 454 ms 70824 KB Output is correct
15 Correct 468 ms 71076 KB Output is correct
16 Correct 485 ms 70564 KB Output is correct
17 Correct 361 ms 57868 KB Output is correct
18 Correct 1707 ms 68028 KB Output is correct
19 Correct 1195 ms 71076 KB Output is correct
20 Correct 279 ms 69280 KB Output is correct
21 Incorrect 2 ms 856 KB Output isn't correct
22 Halted 0 ms 0 KB -