Submission #516097

#	Time	Username	Problem	Language	Result	Execution time	Memory
516097		600Mihnea	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1357 ms	118892 KiB

rings

#include <bits/stdc++.h>

using namespace std;

class DsuClass {
private:
  int n;
  int skip;
  vector<int> t;
  vector<int> deg;
  bool ok;

  int getComponent(int a) {
    assert(0 <= a && a < n);
    if (t[a] == a) return a;
    return t[a] = getComponent(t[a]);
  }


public:

  DsuClass() = default;

  DsuClass(int n, int skip) :
    n(n),
    skip(skip),
    t(n),
    ok(true),
    deg(n, 0) {

    iota(t.begin(), t.end(), 0);
  };

  void unite(int a, int b) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == skip || b == skip) return;
    deg[a]++;
    deg[b]++;
    ok &= (deg[a] <= 2);
    ok &= (deg[b] <= 2);
    ok &= (getComponent(a) != getComponent(b));
    t[getComponent(a)] = getComponent(b);
  }

  bool isOk() {
    return ok;
  }

};

const int N = (int) 1e6 + 7;
int n;
int maxDeg = 0;
int maxDegVertex = 0;
vector<int> g[N];
bool Started = false;
int cycles = 0;
int sizeOfCycle = -1;
int parrent[N];

int root(int a) {
  if (parrent[a] == a) return a;
  return parrent[a] = root(parrent[a]);
}

void Init(int __n__) {

  assert(!Started);
  Started = true;

  n = __n__;


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

bool vis[N];
bool act[N];
int cntActive;

void computeSizeOfCycle(int a, int theParrent = -1) {
  act[a] = true;
  vis[a] = true;
  cntActive++;

  for (auto &b : g[a]) {
    if (act[b] && b != theParrent) {
      assert(sizeOfCycle == -1);
      sizeOfCycle = cntActive;
    }
    if (vis[b]) {
      continue;
    }
    computeSizeOfCycle(b, a);
  }

  cntActive--;
  act[a] = false;
}

queue<pair<int, int>> edgesQueue;

void Link(int a, int b) {
  assert(0 <= a && a < n);
  assert(0 <= b && b < n);

  g[a].push_back(b);
  g[b].push_back(a);

  edgesQueue.push({a, b});

  bool onCycle = (root(a) == root(b));

  if (onCycle) {
    cycles++;
    if (cycles == 1) {
      /// super duper mega fresh new cycle
      sizeOfCycle = -1;
      computeSizeOfCycle(a);
      assert(sizeOfCycle != -1);
    }
  }


  parrent[root(a)] = root(b);

  if ((int) g[a].size() > maxDeg) {
    maxDeg = (int) g[a].size();
    maxDegVertex = a;
  }

  if ((int) g[b].size() > maxDeg) {
    maxDeg = (int) g[b].size();
    maxDegVertex = b;
  }

}

vector<DsuClass> potentials;


int CountCritical() {
  if (maxDeg <= 2) {
    if (cycles == 0) {
      return n;
    }
    if (cycles == 1) {
      return sizeOfCycle;
    }
    if (cycles >= 2) {
      return 0; /// independent cycles are bad for your health
    }
  } else {
    /// maxDeg >= 3
    if (maxDeg == 3) {
      if (potentials.empty()) {
        potentials.push_back(DsuClass(n, maxDegVertex));
        for (auto &a : g[maxDegVertex]) {
          potentials.push_back(DsuClass(n, a));
        }
      }

    } else {
      /// maxDeg >= 4
      if (potentials.empty()) {
        potentials.push_back(DsuClass(n, maxDegVertex));
      }
      if ((int) potentials.size() >= 2) potentials.resize(1);
    }
    while (!edgesQueue.empty()) {
      int a = edgesQueue.front().first, b = edgesQueue.front().second;
      edgesQueue.pop();
      for (auto &v : potentials) {
        v.unite(a, b);
      }
    }
    int solution = 0;
    for (auto &v : potentials) {
      solution += v.isOk();
    }
    return solution;
  }
  return -1;
}

Compilation message (stderr)

rings.cpp: In constructor 'DsuClass::DsuClass(int, int)':
rings.cpp:11:8: warning: 'DsuClass::ok' will be initialized after [-Wreorder]
   11 |   bool ok;
      |        ^~
rings.cpp:10:15: warning:   'std::vector<int> DsuClass::deg' [-Wreorder]
   10 |   vector<int> deg;
      |               ^~~
rings.cpp:24:3: warning:   when initialized here [-Wreorder]
   24 |   DsuClass(int n, int skip) :
      |   ^~~~~~~~

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