Submission #69586

#	Time	Username	Problem	Language	Result	Execution time	Memory
69586		funcsr	Parachute rings (IOI12_rings)	C++17	0 / 100	1212 ms	67164 KiB

rings

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
struct UF {
  vector<int> U, R;
  UF(int N) {
    rep(i, N) U.pb(i), R.pb(1);
  }
  int find(int x) {
    if (U[x]==x)return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x=find(x), y=find(y);
    if(x==y)return;
    if (R[x]<R[y])swap(x,y);
    U[y]=x;
    R[x]+=R[y];
  }
  bool same(int x, int y) {
    return find(x)==find(y);
  }
};

typedef pair<int, int> P;

int N;
UF uf = NULL;
vector<int> G[1000000];
bool deg012 = true;
vector<int> cycles;
vector<int> cand;
void cand_filter(vector<int> seq) {
  sort(all(seq));
  int a = 0, b = 0;
  vector<int> ret;
  while (a<cand.size() && b<seq.size()) {
    if (cand[a]==seq[b])ret.pb(cand[a]), a++, b++;
    else if (cand[a]<seq[b]) a++;
    else b++;
  }
  swap(cand, ret);
}

void Init(int N_) {
  N = N_;
  uf = UF(N);
  rep(i, N) cand.pb(i);
}

void Link(int a, int b) {
  G[a].pb(b);
  G[b].pb(a);
  if (G[a].size() >= 3) deg012 = false;
  if (G[b].size() >= 3) deg012 = false;
  if (G[a].size() == 3) cand_filter({a, G[a][0], G[a][1], G[a][2]});
  if (G[b].size() == 3) cand_filter({b, G[b][0], G[b][1], G[b][2]});
  if (G[a].size() >= 4) cand_filter({a});
  if (G[b].size() >= 4) cand_filter({b});

  if (!deg012) {
    bool same = uf.same(a, b);
    uf.unite(a, b);
    if (same) cycles.pb(uf.R[uf.find(a)]);
  }
}

int ord[1000000], low[1000000];
int R[1000000];

void dfs(int x, int p, int r) {
  ord[x] = low[x] = r;
  if (p == -1) R[x] = -1;

  for (int t : G[x]) if (t != p) {
    if (ord[t] != -1) {
      low[x] = min(low[x], ord[t]);
      continue;
    }
    dfs(t, x, r+1);
    low[x] = min(low[x], low[t]);
    if (p == -1 || low[t] >= ord[x]) R[x]++;
  }
}

int CountCritical() {
  if (deg012) {
    if (cycles.size() == 0) return N;
    else if (cycles.size() == 1) return cycles[0];
    else return 0;
  }
  if (cand.size() == 0) return 0;
  rep(i, N) ord[i] = low[i] = -1, R[i] = 0;
  int r_def = 0;
  rep(i, N) if (ord[i] == -1) dfs(i, -1, 0), r_def++;

  int deg0 = 0, deg1 = 0, deg3 = 0;
  auto add = [&](int d) {
    if      (d == 0) deg0++;
    else if (d == 1) deg1++;
    else if (d >= 3) deg3++;
  };
  auto rem = [&](int d) {
    if      (d == 0) deg0--;
    else if (d == 1) deg1--;
    else if (d >= 3) deg3--;
  };
  rep(i, N) add(G[i].size());

  int ctr = 0;
  for (int x : cand) {
    rem(G[x].size());
    for (int t : G[x]) {
      rem(G[t].size());
      add(G[t].size()-1);
    }

    assert(deg3 == 0);
    if (2*((r_def+R[x])-deg0) == deg1) ctr++;

    for (int t : G[x]) {
      rem(G[t].size()-1);
      add(G[t].size());
    }
    add(G[x].size());
  }
  return ctr;
}

Compilation message (stderr)

rings.cpp:36:9: warning: passing NULL to non-pointer argument 1 of 'UF::UF(int)' [-Wconversion-null]
 UF uf = NULL;
         ^~~~
rings.cpp: In function 'void cand_filter(std::vector<int>)':
rings.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a<cand.size() && b<seq.size()) {
          ~^~~~~~~~~~~~
rings.cpp:45:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (a<cand.size() && b<seq.size()) {
                           ~^~~~~~~~~~~

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