Submission #231914

#	Time	Username	Problem	Language	Result	Execution time	Memory
231914		AlexLuchianov	Parachute rings (IOI12_rings)	C++14	52 / 100	137 ms	17792 KiB

rings

#include <iostream>
#include <vector>
#include <algorithm>

int const nmax = 100000;

struct Dsu{
  std::vector<int> mult;
  std::vector<int> sz;

  Dsu(int n = 0){
    mult.resize(1 + n);
    sz.resize(1 + n);
    for(int i = 1;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){
    gala = jump(gala);
    galb = jump(galb);
    if(gala == galb)
      return ;
    if(sz[galb] < sz[gala])
      std::swap(gala, galb);
    sz[galb] += sz[gala];
    mult[gala] = galb;
  }

  int getsize(int gala){
    return sz[jump(gala)];
  }

  bool connected(int gala, int galb){
    return (jump(gala) == jump(galb));
  }
};

struct Ring{
  int avoid;
  std::vector<int> grade;
  int iscycle, isgreat;
  int cyclesize = 0;

  int n;
  Dsu mp;

  Ring(int n_ = 0, int avoid_ = 0){
    n = n_;
    grade.resize(1 + n);
    avoid = avoid_;
    iscycle = isgreat = 0;
    mp = Dsu(n);
  }

  void unite(int gala, int galb){
    if(gala == avoid || galb == avoid)
      return ;
    if(mp.connected(gala, galb) == 1) {
      iscycle++;
      cyclesize = mp.getsize(gala);
    }

    mp.unite(gala, galb);
    grade[gala]++;
    grade[galb]++;
    if(grade[gala] == 3 || grade[galb] == 3)
      isgreat = 1;
  }

  bool valid(){
    return ((0 == iscycle) && (0 == isgreat));
  }
};


int N, phase = 1;
Ring universal;
int result;

void Init(int N_) {
  N = N_;
  result = N;
  universal = Ring(N, 0);
}


std::vector<std::pair<int,int>> edges;
std::vector<int> g[1 + nmax];
std::vector<std::pair<int,Ring> > cand;


void Link(int a, int b) {
  ++a;
  ++b;
  edges.push_back({a, b});
  g[a].push_back(b);
  g[b].push_back(a);

  universal.unite(a, b);

  if(phase < 3 && universal.isgreat == 1){
    phase = 3;
    std::vector<int> temp;
    for(int h = 0; h < g[a].size(); h++)
      temp.push_back(g[a][h]);
    for(int h = 0; h < g[b].size(); h++)
      temp.push_back(g[b][h]);
    std::sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());

    for(int i = 0; i < temp.size(); i++){
      cand.push_back({temp[i], Ring(N, temp[i])});
      for(int j = 0; j < edges.size(); j++)
        cand[i].second.unite(edges[j].first, edges[j].second);
    }

  } else if(phase == 3){
    for(int i = 0; i < cand.size(); i++)
      cand[i].second.unite(a, b);
  } else if(1 < universal.iscycle){
    result = 0;
  } else if(phase == 1 && 1 == universal.iscycle){
    phase = 2;
    result = universal.cyclesize;
  }
}

int CountCritical() {
  if(phase < 3)
    return result;
  else {
    result = 0;
    for(int i = 0; i < cand.size(); i++)
      result += cand[i].second.valid();
    return result;
  }
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[a].size(); h++)
                    ~~^~~~~~~~~~~~~
rings.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[b].size(); h++)
                    ~~^~~~~~~~~~~~~
rings.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < temp.size(); i++){
                    ~~^~~~~~~~~~~~~
rings.cpp:121:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < edges.size(); j++)
                      ~~^~~~~~~~~~~~~~
rings.cpp:126:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cand.size(); i++)
                    ~~^~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:141:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cand.size(); i++)
                    ~~^~~~~~~~~~~~~

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