Submission #600220

#	Time	Username	Problem	Language	Result	Execution time	Memory
600220		MilosMilutinovic	Parachute rings (IOI12_rings)	C++14	100 / 100	1846 ms	111388 KiB

rings

/**
 *    author:  wxhtzdy
 *    created: 18.07.2022 00:00:16
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

const int MAXN = 1000005;

vector<int> g[MAXN];
int vis[MAXN];
int prv[MAXN];
int deg[4][MAXN];
int good[MAXN];
int ver[4];

vector<int> cyc;
vector<pair<int, int>> edges;

vector<dsu> f(4, dsu(MAXN));

int state, ans;
dsu d(MAXN);

void state1(int v) {
  state = 1;
  ans = 0;
  for (int i = 0; i < MAXN; i++) {
    if (d.get(i) == d.get(v)) {
      ans += 1;
    }
  }
}

void state2(int i) {
  ver[0] = i;
  assert((int) g[i].size() == 3);
  for (int j = 0; j < (int) g[i].size(); j++) {
    ver[1 + j] = g[i][j];
  }
  for (int i = 0; i < 4; i++) {
    good[i] = true;
  } 
  for (auto& p : edges) {
    int u = p.first;
    int v = p.second;
    for (int i = 0; i < 4; i++) {
      if (ver[i] == u || ver[i] == v) {
        continue;
      }
      ++deg[i][u];
      ++deg[i][v];
      if (deg[i][u] >= 3) {
        good[i] = false;
      }      
      if (deg[i][v] >= 3) {
        good[i] = false;
      }
      if (!f[i].unite(u, v)) {
        good[i] = false;
      }
    }
  }
  state = 2;                     
}

void state3() {
  state = 3;
  ans = 0;
}

void Init(int n) {
  state = 0;
  ans = n;
}

void Link(int a, int b) {
  g[a].push_back(b);
  g[b].push_back(a);
  edges.emplace_back(a, b);
  if (state == 0 || state == 1) {
    if (d.unite(a, b)) {
      if ((int) g[a].size() >= 3) {
        state2(a);
      } else if ((int) g[b].size() >= 3) {
        state2(b);
      }
    } else {
      if (state == 0) {
        state1(a);   
      } else {
        state3();
      }
    }
  } else if (state == 2) {
    for (int i = 0; i < 4; i++) {
      if (ver[i] == a || ver[i] == b) {
        continue;
      }
      ++deg[i][a];
      ++deg[i][b];
      if (deg[i][a] >= 3) {
        good[i] = false;
      }      
      if (deg[i][b] >= 3) {
        good[i] = false;
      }
      if (!f[i].unite(a, b)) {
        good[i] = false;
      }
    }   
  }
} 

int CountCritical() {
  if (state == 2) {
    ans = 0;
    for (int i = 0; i < 4; i++) {
      if (good[i]) {
        ans += 1;
      }
    }
  }
  return ans;
}

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