Submission #592873

#	Time	Username	Problem	Language	Result	Execution time	Memory
592873		MohamedFaresNebili	Parachute rings (IOI12_rings)	C++14	52 / 100	1484 ms	262144 KiB

rings

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound

                int N, P[1000001], C[1000001], S[1000001];
                vector<int> adj[1000001], R;
                set<int> res;
                bool vis[1000001];

                int findSet(int v) {
                    if(P[v] == v) return v;
                    return P[v] = findSet(P[v]);
                }
                void unionSet(int u, int v) {
                    u = findSet(u), v = findSet(v);
                    if(u == v) return;
                    P[v] = u; S[u] += S[v];
                }
                void Init(int n) {
                    N = n;
                    for(int l = 0; l < N; l++)
                        P[l] = l, res.insert(l);
                }
                void solve(set<int> cur) {
                    auto it = cur.begin(); set<int> New;
                    while(it != cur.end()) {
                        if(res.count(*it))
                            New.insert(*it);
                        it++;
                    }
                    swap(New, res);
                }
                bool dfs(int v, int p, int d) {
                    C[v] = p; vis[v] = 1;
                    R.push_back(v);
                    if(v == d) {
                        set<int> cur;
                        cur.insert(v); v = C[v];
                        while(v != d) {
                            cur.insert(v); v = C[v];
                        }
                        solve(cur);
                        return 1;
                    }
                    for(auto u : adj[v]) {
                        if(u == p || vis[u]) continue;
                        if(dfs(u, v, d)) return 1;
                    }
                    return 0;
                }
                void Link(int A, int B) {
                    int U = findSet(A), V = findSet(B);
                    adj[A].push_back(B);
                    adj[B].push_back(A);

                    if(U == V) {
                        S[U]++;
                        if(S[U] <= 3) dfs(A, B, B);
                        for(auto u : R) vis[u] = 0;
                        R.clear();

                        if(S[U] == 2) {
                            set<int> New;
                            auto it = res.begin();
                            while(it != res.end()) {
                                if(adj[*it].size() >= 3)
                                    New.insert(*it);
                                it++;
                            }
                            swap(New, res);
                        }

                    }
                    else unionSet(U, V);

                    set<int> New;
                    if(adj[A].size() == 4)
                        New.clear(), New.insert(A), solve(New);
                    if(adj[B].size() == 4)
                        New.clear(), New.insert(B), solve(New);
                    if(adj[A].size() == 3) {
                        New.clear(); New.insert(A);
                        for(auto u : adj[A])
                            New.insert(u);
                        solve(New);
                    }
                    if(adj[B].size() == 3) {
                        New.clear(); New.insert(B);
                        for(auto u : adj[B])
                            New.insert(u);
                        solve(New);
                    }
                }
                int CountCritical() {
                    return res.size();
                }

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