Submission #752589

#	Time	Username	Problem	Language	Result	Execution time	Memory
752589		marvinthang	Parachute rings (IOI12_rings)	C++17	100 / 100	733 ms	60836 KiB

rings

/*************************************
*    author: marvinthang             *
*    created: 03.06.2023 15:50:54    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

struct DisjointSet {
    
    int n, max_deg;
    int cycle;
    vector <int> lab, deg;

    DisjointSet(int _n = 0) {
        n = _n; max_deg = 0; cycle = -1;
        lab.assign(n, -1);
        deg.assign(n, 0);
    }

    int find(int u) {
        return lab[u] < 0 ? u : lab[u] = find(lab[u]);
    }

    bool join(int u, int v) {
        int a = ++deg[u], b = ++deg[v];
        maximize(max_deg, max(a, b));
        if (max_deg > 2) cycle = 0;
        u = find(u); v = find(v);
        if (u == v) {
            if (cycle == -1) cycle = -lab[u];
            else cycle = 0;
            return false;
        }
        if (lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }
};

using DSU = DisjointSet;

// end of template

const int MAX = 1e6 + 6;

int N, del[5];
bool tran;
DSU dsu[5];
vector <pair <int, int>> edges;

void Init(int N_) {
    N = N_;
    REP(i, 5) dsu[i] = DSU(N);
}

void Link(int A, int B) {
    if (!tran) {
        edges.emplace_back(A, B);
        dsu[0].join(A, B);
        if (dsu[0].max_deg > 2) {
            REP(u, N) if (dsu[0].deg[u] > 2) {
                del[1] = u;
                int t = 1;
                for (auto [x, y]: edges) {
                    if (x == u) del[++t] = y;
                    if (y == u) del[++t] = x;
                }
                assert(t == 4);
                break;
            }
            FOR(i, 1, 5) {
                for (auto [u, v]: edges) if (u != del[i] && v != del[i]) dsu[i].join(u, v);
            }
            tran = true;
        }
    } else {
        FOR(i, 1, 5) if (A != del[i] && B != del[i]) dsu[i].join(A, B);
    }
}

int CountCritical() {
    if (!tran) return dsu[0].cycle == -1 ? N : dsu[0].cycle;
    int cnt = 0;
    FOR(i, 1, 5) cnt += dsu[i].cycle == -1;
    return cnt;
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

void Init(int N);
int CountCritical();
void Link(int a, int b);

int main() {
    file("rings");
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);

  int N, L;
  tmp = scanf("%d %d", &N, &L);
  assert(tmp == 2);
  Init(N);

  int i;
  for (i = 0; i < L; i++) {
    int A, B;
    tmp = scanf("%d", &A);
    if (A == -1) {
      int critical;
      critical = CountCritical();
      printf("%d\n", critical);
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;

}
#endif

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