Submission #635509

#	Time	Username	Problem	Language	Result	Execution time	Memory
635509		Bruteforceman	Parachute rings (IOI12_rings)	C++11	100 / 100	639 ms	55632 KiB

rings

    #pragma GCC optimize("Ofast")    
    #include "bits/stdc++.h"
    using namespace std;
    int N;
    struct dsu {
        int other[1000010];
        int len[1000010];
        int cycle_cnt;
        int cycle_sum;
        bool bad;
        int no_of_nodes;
        int del_node;
     
        void init (int n) {
            no_of_nodes = n;
            del_node = -1;
            for(int i = 0; i < no_of_nodes; i++) {
                other[i] = i;
                len[i] = 1;
            }
            cycle_cnt = 0;
            cycle_sum = 0;
            bad = false;
        }
        void add(int x, int y) {
            if(del_node == x || del_node == y) return ; 
            if(bad) return ;
            if(other[x] == y) {
                other[x] = -1;
                other[y] = -1;
                cycle_cnt += 1;
                cycle_sum += len[x];
            } else {
                if(other[x] == -1 || other[y] == -1) {
                    bad = true;
                    return ;
                }
                int p = other[y];
                int q = other[x];
                other[p] = q;
                other[q] = p;
                int sum = len[x] + len[y];
                len[p] = len[q] = sum;
                if(x != p && x != q) {
                    other[x] = -1;
                }
                if(y != p && y != q) {
                    other[y] = -1;
                }
            }
        }
        int count() {
            if(bad) return 0;
            if(cycle_cnt <= 1) {
                if(cycle_cnt == 1) return cycle_sum;
                else return no_of_nodes;
            }
            return 0;
        }
    } T[4];
    int deg[1000010];
    vector <int> l, r;
    bool found_cand;
     
    void Init(int N_) {
      N = N_;
      T[0].init(N);
      for(int i = 0; i < N; i++) {
        deg[i] = 0;
      }
      l.clear(); r.clear();
      found_cand = false;
    }
    void Link(int A, int B) {
        if(found_cand) {
            for(int i = 0; i < 4; i++) {
                T[i].add(A, B);
            }
            return ;
        }
        ++deg[A]; ++deg[B];
        l.emplace_back(A);
        r.emplace_back(B);
        if(deg[A] == 3 || deg[B] == 3) {
            vector <int> v;
            int can = deg[A] == 3 ? A : B;
            v.emplace_back(can);
            for(int i = 0; i < (int) l.size(); i++) {
                if(l[i] == can || r[i] == can) {
                    v.emplace_back(l[i] ^ r[i] ^ can);
                }
            }
            for(int i = 0; i < 4; i++) {
                T[i].init(N);
                T[i].del_node = v[i];
            }
            found_cand = true;
        } else {
            T[0].add(A, B);
        }
        if(found_cand) {
            for(int i = 0; i < (int)l.size(); i++) {
                Link(l[i], r[i]);
            }
            l.clear(); r.clear();
        }
    }
     
    int CountCritical() {
        if(found_cand) {
            int ans = 0;
            for(int i = 0; i < 4; i++) {
                if(T[i].cycle_cnt == 0 && !T[i].bad) {
                    ++ans;
                }
            }
            return ans;
        }
        return T[0].count();
    }

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