Submission #680446

#	Time	Username	Problem	Language	Result	Execution time	Memory
680446		cadmiumsky	Parachute rings (IOI12_rings)	C++14	100 / 100	1653 ms	141092 KiB

rings

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
//#define int ll
#define sz(x) (int)(x).size() 

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e6 + 5;

int n;

struct DSU {
  int forb;
  int dsu[nmax], area[nmax];
  int grad[nmax];
  
  bool fail = 0;
  int f(int x) { return (dsu[x] == x? x : dsu[x] = f(dsu[x])); }
  void unite(int x, int y) {
    if(x == forb || y == forb) return;
    // cerr << x << ' ' << y << ' ' << forb << '\t';
    grad[x]++;
    grad[y]++;
    if(grad[x] > 2 || grad[y] > 2)
      fail = 1;
    x = f(x);
    y = f(y);
    // cerr << x << ' ' << y << '\n';
    if(x == y) { fail = 1; return; }
    dsu[x] = y;
    area[y] += area[x];
  }
  void init(int n, vector<pii> edg, int interz = -1) {
    forb = interz;
    for(int i = 0; i < n; i++)
      dsu[i] = i, area[i] = 1, grad[i] = 0;
    for(auto [a, b] : edg)
      unite(a, b);
  }
  bool query() { return !fail; }
};

namespace Finite {
  int freq[nmax];
  vector<DSU> dlist;
  int mgrad = 0;
  int precrez = n;
  vector<pii> edg;
  
  vector<int> g[nmax];
  
  void init3(int a) {
    dlist.clear();
    for(auto x : g[a])
      dlist.resize(sz(dlist) + 1),
      dlist.back().init(n, edg, x);    
    dlist.resize(sz(dlist) + 1),
    dlist.back().init(n, edg, a);
    return;
  }
  void init4(int a) {
    dlist.clear();
    dlist.resize(sz(dlist) + 1),
    dlist.back().init(n, edg, a);
    return;
  }
  
  void upd(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
    edg.emplace_back(a, b);
    
    int fmgrad = mgrad;
    freq[a]++;
    freq[b]++;
    mgrad = max({mgrad, freq[a], freq[b]});
    if(fmgrad != mgrad) {
      if(mgrad == 3)
        init3(freq[a] == 3? a : b);
      if(mgrad == 4)
        init4(freq[a] == 4? a : b);
      if(mgrad > 2) return;
    }
    if(mgrad == 2) {
      // cerr << a << ' ' << b << '\n';
      // cerr << dlist[0].f(a) << ' ' << dlist[0].f(b) << '\n';
      if(dlist[0].f(a) == dlist[0].f(b)) {
        if(precrez == n) {
          // cerr << "lamborghini\n";
          precrez = dlist[0].area[dlist[0].f(a)];
        }
        else
          precrez = 0;
      }
    }
    for(auto &x : dlist)
      x.unite(a, b);
    return;
  }
  int get() {
    if(mgrad >= 3) {
      int sum = 0;
      for(auto &x : dlist)
        sum += x.query();
      return sum;
    }
    else
      return precrez;
  }
  void init() {
    precrez = n;
    dlist.resize(1);
    dlist.back().init(n, edg);
  }
  
}

void Init(int N) {
  n = N;
  Finite::init();
}
void Link(int A, int B) {
  Finite::upd(A, B);
  //cerr << " > " << Finite::get() << '\n';
}
int CountCritical() {
  //cerr << Finite::state << '\t';
  return Finite::get();
}

Compilation message (stderr)

rings.cpp: In member function 'void DSU::init(int, std::vector<std::pair<int, int> >, int)':
rings.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [a, b] : edg)
      |              ^

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