Submission #254420

#	Time	Username	Problem	Language	Result	Execution time	Memory
254420		sandoval	낙하산 고리들 (IOI12_rings)	C++11	0 / 100	4105 ms	173292 KiB

rings

#include <bits/stdc++.h>

using namespace std;
using ii = pair<int,int>;
using ll = long long;

constexpr int MAXN = 5+1e6;

struct dsu {
private:
vector<int> f,sz;
public:
dsu() = default;
void reset(int n) {
  sz.assign(n, 1); f.resize(n);
  for (int i = 0; i < n; ++i) f[i] = i;
}
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
bool join(int x, int y) {
  if ((x = find(x)) == (y = find(y))) return false;
  if (sz[x] < sz[y]) swap(x,y);
  sz[x] += sz[y];
  f[y] = x;
  return true;
}};

namespace data {
vector<ii> history; // OK!
set<int> active; // OK!

int deg[MAXN]; // OK!
dsu* graphs[MAXN]; // OK!

set<int> byd[5]; // OK!
int phase; // OK!
dsu general; // OK!

int N; // OK!
vector<int> G[MAXN]; // OK!

bool visited[MAXN]; // OK!

bool okPhase2; // OK!
vector<int> endPointsPhase2; // OK!

int degPhase3[MAXN], rootPhase3;
bool okPhase3;

int* degPhase4[MAXN];
bool initPhase4[MAXN]; // OK!
bool okPhase4[MAXN];


void keep_only(const set<int>& keep) {
  for (set<int>::iterator it = active.begin(), nx; it != active.end(); it = nx) {
    nx = next(it);
    if (keep.find(*it) == keep.end()) {
      active.erase(it);
    }
  }
}

void initializePhase3(int u) {
  // assert(graphs[u] == nullptr);
  okPhase3 = true;
  rootPhase3 = u;
  for (int i = 0; i < N; ++i) {
    degPhase3[i] = 0;
  }

  graphs[u] = new dsu();
  graphs[u]->reset(N);
  for (auto x : history) {
    if (x.first == u || x.second == u) continue;
    okPhase3 &= (++degPhase3[x.first] <= 2);
    okPhase3 &= (++degPhase3[x.second] <= 2);
    okPhase3 &= (graphs[rootPhase3]->join(x.first, x.second));
  }

  if (!okPhase3) {
    keep_only({});
  }
}
void initPhase4PerNode(int u) {
  // assert(!initPhase4[u]);
  // assert(degPhase4[u] == nullptr);

  initPhase4[u] = true;
  okPhase4[u] = true;
  graphs[u] = new dsu(); graphs[u]->reset(N);
  degPhase4[u] = new int[N];
  for (int i = 0; i < N; ++i) degPhase4[u][i] = 0;

  for (auto x : history) {
    if (x.first == u || x.second == u) continue;
    okPhase4[u] &= (++degPhase4[u][x.first] <= 2);
    okPhase4[u] &= (++degPhase4[u][x.second] <= 2);
    okPhase4[u] &= (graphs[u]->join(x.first, x.second));
  }
}
void restart_visit() {
  fill(visited, visited+N, false);
}
void reset(int n) {
  N=n;
  history.clear();
  active.clear();

  for (int i = 0; i < 5; ++i) byd[i].clear();
  for (int i = 0; i < n; ++i) {
    deg[i] = 0;
    G[i].clear();
    if (graphs[i] != nullptr) {
      delete graphs[i];
      graphs[i] = nullptr;
    }
    if (degPhase4[i] != nullptr) {
      delete degPhase4[i];
      degPhase4[i] = nullptr;
    }

    active.insert(i);
    byd[0].insert(i);
    initPhase4[i] = false;
  }
  phase = 1;
  general.reset(n);
  okPhase2 = true;
  endPointsPhase2.clear();
}}

void Init(int N) {
  data::reset(N);
}

bool dfs(int A, int B, set<int>& path) {
  data::visited[A] = true;
  if (A == B) {
    path.insert(A);
    return true;
  }

  for (int v : data::G[A]) {
    if (!data::visited[v] && dfs(v, B, path)) {
      path.insert(A);
      return true;
    }
  }
  return false;
}

void Link(int A, int B) {
  data::history.push_back({A,B});

  using namespace data;
  if (active.empty()) return;

  byd[deg[A]].erase(A);
  byd[deg[B]].erase(B);

  deg[A] = min(1+deg[A], 4);
  deg[B] = min(1+deg[B], 4);

  byd[deg[A]].insert(A);
  byd[deg[B]].insert(B);

  int largest = -1;
  for (int i = 4; i >= 0; --i) {
    if ((int)byd[i].size() >= 1) {
      largest = i;
      break;
    }
  }

  assert(largest != -1);
  if (phase == 1) {
    assert(largest >= 0 && largest <= 2);
    if (largest == 2) phase = 2;
  } else if (phase == 2) {
    assert(largest >= 2);
    if (largest == 3) phase = 4;
  } else if (phase == 4) {
    assert(largest >= 3);
    if (largest == 4) phase = 5;
  }

  if (phase == 1) {
    //cout << "Phase 1" << endl;
    // assert(general.join(A,B));
    G[A].push_back(B);
    G[B].push_back(A);
  } else if (phase == 2) {
    //cout << "Phase 2" << endl;
    bool f = general.join(A,B);
    if (!f) {
      if (okPhase2) {
        set<int> path;
        restart_visit();
        dfs(A,B,path);
        keep_only(path);
        okPhase2 = false;
        endPointsPhase2.push_back(A);
        endPointsPhase2.push_back(B);
      } else {
        auto it = find(endPointsPhase2.begin(), endPointsPhase2.end(), A);
        auto it2 = find(endPointsPhase2.begin(), endPointsPhase2.end(), B);
        vector<int>::iterator de = endPointsPhase2.end();

        if (it != endPointsPhase2.end()) {
          de = it;
          endPointsPhase2.erase(it2);
        } else if (it2 != endPointsPhase2.end()) {
          de = it2;
          endPointsPhase2.erase(it);
        } else {
          keep_only({});
          endPointsPhase2.clear();
        }

        if (de != endPointsPhase2.end()) {
          keep_only({*de});
          initializePhase3(*de);
          phase = 3;
        }
      }
    }

    G[A].push_back(B);
    G[B].push_back(A);
  } else if (phase == 3) {
    if (A == rootPhase3 || B == rootPhase3) return;
    okPhase3 &= graphs[rootPhase3]->join(A,B);
    okPhase3 &= (++degPhase3[A] <= 2);
    okPhase3 &= (++degPhase3[B] <= 2);
    if (!okPhase3) keep_only({});
  } else if (phase == 4) {
    G[A].push_back(B);
    G[B].push_back(A);
    const int sz = (int)byd[3].size();
    assert(sz>0);
    int fNode = *byd[3].begin();
    set<int> check;

    if (sz >= 5) {
      keep_only({});
    } else if (sz >= 1 && sz <= 4) {
      for (auto x : G[fNode]) {
        bool ok = true;
        for (auto u : byd[3]) {
          if (find(G[u].begin(), G[u].end(), x) == G[u].end()) {
            ok = false;
            break;
          }
        }

        if (ok) {
          check.insert(x);
        }
      }
      for (auto u : byd[3]) check.insert(u);
    } else {
      // assert(false);
    }

    keep_only(check);
    set<int> keep;

    for (auto x : active) {
      if (!initPhase4[x]) {
        initPhase4PerNode(x);
      } else {
        if (A != x && B != x) {
          okPhase4[x] &= (++degPhase4[x][A] <= 2);
          okPhase4[x] &= (++degPhase4[x][B] <= 2);
          okPhase4[x] &= (graphs[x]->join(A,B));
        }
      }

      if (okPhase4[x]) {
        keep.insert(x);
      }
    }

    keep_only(keep);
  } else if (phase == 5) {
    assert(!byd[4].empty());
    if ((int)byd[4].size() == 1) {
      keep_only({*byd[4].begin()});
      initializePhase3(*byd[4].begin());
      phase = 3;
    } else if ((int)byd[4].size() >= 2) {
      keep_only({});
    }
  }
}

int CountCritical() {
  return (int)data::active.size();
}

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