Submission #169255

#	Time	Username	Problem	Language	Result	Execution time	Memory
169255		AlexLuchianov	Parachute rings (IOI12_rings)	C++14	20 / 100	4041 ms	7800 KiB

rings

#include <vector>
#include <algorithm>

using namespace std;
int const nmax = 100000;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

vector<int> g[1 + nmax];
int type[1 + nmax];

namespace Dsu{
  int mult[1 + nmax];
  int sz[1 + nmax];
  void initialize(int n){
    for(int i = 0; i < n; i++) {
      mult[i] = i;
      sz[i] = 1;
    }
  }
  int jump(int gala){
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }
  void unite(int gala, int galb, int newtype){
    gala = jump(gala);
    galb = jump(galb);
    if(sz[galb] < sz[gala])
      swap(gala, galb);
    if(gala != galb) {
      mult[gala] = galb;
      sz[galb] += sz[gala];
    }
    type[galb] = newtype;
  }
}

int N, result;
int phase = 1;

vector<int> candidates;
int seen[1 + nmax];

void dfs(int node, int parent, bool &cycle, int deleted){
  seen[node] = 1;
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(to != parent && to != deleted) {
      if(seen[to] == 1)
        cycle = 1;
      else
        dfs(to, node, cycle, deleted);
    }
  }
}

bool test(int deleted){
  for(int i = 0; i < N; i++)
    seen[i] = 0;
  bool cycle = 0;
  for(int i = 0; i < N; i++)
    if(i != deleted && seen[i] == 0)
      dfs(i, -1, cycle, deleted);
  if(cycle == 1)
    return false;

  for(int i = 0; i < N; i++) {
    int degree = 0;
    if(i != deleted){
      for(int h = 0; h < g[i].size(); h++)
        if(g[i][h] != deleted)
          degree++;
      if(2 < degree)
        return false;
    }
  }
  return true;
}

void computecandidates(){
  sort(candidates.begin(), candidates.end());
  candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

  vector<int> newcand;
  for(int i = 0; i < N; i++)
    if(test(i) == 1)
      newcand.push_back(i);
  candidates = newcand;
  result = candidates.size();
}

void Init(int N_) {
  N = N_;
  Dsu::initialize(N);
  for(int i = 0; i < N; i++)
    type[i] = 1;
  result = N;
}

void Link(int a, int b) {
  if(result == 0)
    return ;

  int gala = Dsu::jump(a);
  int galb = Dsu::jump(b);
  g[a].push_back(b);
  g[b].push_back(a);
  if(type[galb] < type[gala]){
    swap(a, b);
    swap(gala, galb);
  }

  if(gala != galb && g[a].size() <= 2 && g[b].size() <= 2) {
    Dsu::unite(gala, galb, type[galb]);
    return ;
  }


  if(phase == 1){
    if(gala == galb && g[a].size() <= 2 && g[b].size() <= 2){
      Dsu::unite(gala, galb, 2);
      phase = 2;
      result = Dsu::sz[galb];
    } else {
      Dsu::unite(gala, galb, 3);
      phase = 3;
      for(int h = 0; h < g[a].size(); h++)
        candidates.push_back(g[a][h]);
      for(int h = 0; h < g[b].size(); h++)
        candidates.push_back(g[b][h]);
      computecandidates();
    }
  } else if(phase == 2){
    Dsu::unite(gala, galb, 3);
    phase = 3;
    for(int h = 0; h < g[a].size(); h++)
      candidates.push_back(g[a][h]);
    for(int h = 0; h < g[b].size(); h++)
      candidates.push_back(g[b][h]);
    computecandidates();
  } else if(phase == 3){
    Dsu::unite(gala, galb, 3);
    if(1 < candidates.size())
      computecandidates();
    else if(candidates[0] == b)
      return ;
  }
}

int CountCritical() {
  return result;
}

Compilation message (stderr)

rings.cpp: In function 'void dfs(int, int, bool&, int)':
rings.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'bool test(int)':
rings.cpp:72:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[i].size(); h++)
                      ~~^~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:129:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[a].size(); h++)
                      ~~^~~~~~~~~~~~~
rings.cpp:131:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[b].size(); h++)
                      ~~^~~~~~~~~~~~~
rings.cpp:138:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[a].size(); h++)
                    ~~^~~~~~~~~~~~~
rings.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[b].size(); h++)
                    ~~^~~~~~~~~~~~~

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