Submission #1183058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183058		countless	Parachute rings (IOI12_rings)	C++20	Compilation error	0 ms	0 KiB

rings

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;

// greatest best, U F D S
struct DSU {
    int n;
    vector<int> parent, size;
    vector<bool> conn;

    DSU(int n) : n(n) {
        conn.assign(n, false);
        size.assign(n, 1);
        parent.resize(n);

        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    bool check(int u, int v) {
        u = find(u), v = find(v);
        return u == v;
    }
    
    int find(int u) {
        if (parent[u] == u)
            return u;
        return parent[u] = find(parent[u]);
    }

    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v)
            return true;
        
        parent[v] = u;
        size[u] += size[v];

        return false;
    }
};

struct state {
    int mx;
    bool flag;
    DSU *dsu;
    vector<int> adj;

    state(int mx = 0, bool flag = false) : mx(mx), flag(flag) {
        dsu = new DSU(n);
        adj.resize(n);
    }
};


int ans, mx;
vector<vector<int>> adj;
bool flag, stop;
set<int> can;
hash_map<int, state> rem;
DSU *dsu;

void Init(int N_) {
    n = ans = N_;
    mx = flag = stop = 0;
    adj.resize(n);
    dsu = new DSU(n);

    for (int i = 0; i < n; i++) {
        can.insert(i);
    }
}

// N->L->4->3->2->1->0
void Link(int u, int v) {
    if (stop) {
        return;
    }

    adj[u].push_back(v);
    adj[v].push_back(u);

    mx = max(mx, (int)adj[u].size());
    mx = max(mx, (int)adj[v].size());

    // trivial (no components are more than pairs)
    if      (mx == 1) {
        dsu->unite(u, v);
    }

    // check for L
    else if (mx == 2) {
        // already in the same component
        if (dsu->unite(u, v)) {
            // there already exists a loop
            if (flag) {
                can.clear();
                ans = can.size();
            }

            // because mx == 2, this is a loop
            else {
                can.clear();
    
                for (int i = 0; i < n; i++) {
                    if (dsu->check(u, i)) {
                        can.insert(i);
                    }
                }
    
                ans = can.size();
                flag = 1;
            }
        }

        // only lines
        else {
            // nothing
            ;;
        }
    }

    // there is a lot of casework here
    else if (mx == 3) {
        // if either of the two are new candidates
        // check if they are in the same component as can
        if (adj[u].size() == 3) {
            set<int> temp;
            if (can.count(u)) {
                temp.insert(u);
            }

            for (auto &w : adj[u]) {
                if (can.count(w)) {
                    temp.insert(w);
                }
            }

            can = temp;
        }

        if (adj[v].size() == 3) {
            set<int> temp;
            if (can.count(v)) {
                temp.insert(v);
            }

            for (auto &w : adj[v]) {
                if (can.count(w)) {
                    temp.insert(w);
                }
            }

            can = temp;
        }

        dsu->unite(u, v);
    }

    // there is only one candidate
    else if (mx >= 4) {
        if (adj[u].size() == 3) {
            set<int> temp;
            if (can.count(u)) {
                temp.insert(u);
            }

            for (auto &w : adj[u]) {
                if (can.count(w)) {
                    temp.insert(w);
                }
            }

            can = temp;
        }

        else if (adj[u].size() > 3) {
            can.clear();
            if (can.count(u)) {
                can.insert(u);
            }
        }

        if (adj[v].size() == 3) {
            set<int> temp;
            if (can.count(v)) {
                temp.insert(v);
            }

            for (auto &w : adj[v]) {
                if (can.count(w)) {
                    temp.insert(w);
                }
            }

            can = temp;
        }

        
        else if (adj[v].size() > 3) {
            can.clear();
            if (can.count(v)) {
                can.insert(v);
            }
        }
        
        dsu->unite(u, v);
    }

    // simulate removing vertices
    if (mx >= 3) {
        ans = 0;
        for (auto &w : can) {
            if (rem.count(w)) {
                // no need to process unite
                if (u == w || v == w) {
                    if (!rem[w].flag && rem[w].mx <= 2)
                        ans++;
                }

                else {
                    rem[w].adj[u]++;
                    rem[w].adj[v]++;
                    rem[w].mx = max(rem[w].mx, max(rem[w].adj[u], rem[w].adj[v]));

                    if (rem[w].dsu->unite(u, v)) {
                        rem[w].flag = true;
                    }
   
                    // check
                    if (!rem[w].flag && rem[w].mx <= 2)
                        ans++;
                }
            }

            // init
            else {
                rem[w] = state();
                for (int i = 0; i < n; i++) {
                    if (i == w)
                        continue;
                    for (auto &j : adj[i]) {
                        if (j == w)
                            continue;
                        if (j > i)
                            continue;

                        rem[w].adj[i]++;
                        rem[w].adj[j]++;
                        rem[w].mx = max(rem[w].mx, max(rem[w].adj[i], rem[w].adj[j]));
    
                        if (rem[w].dsu->unite(i, j)) {
                            rem[w].flag = true;
                        }
                    }
                }

                // check
                if (!rem[w].flag && rem[w].mx <= 2)
                    ans++;
            }

            // cerr << rem[w].flag << " " << rem[w].mx << endl;
        }
    }

    if (ans == 0) {
        stop = true;
    }
}

int CountCritical() {
    return ans;
}

int main() {
    int n, l; cin >> n >> l;
    Init(n);
    for (int i = 0; i < l; i++) {
        int a, b; cin >> a;
        if (a == -1) {
            cout << CountCritical() << endl;
        } else {
            cin >> b;
            Link(a, b);
        }
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDgD96V.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccWDnaDP.o:rings.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status