Submission #1052770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052770		clementine	Parachute rings (IOI12_rings)	C++17	0 / 100	319 ms	74100 KiB

rings

#include <bits/stdc++.h>
using namespace std;


int N;
struct Point{
  int parent;
  int sz;
};
Point points[1000006];

void construct(int n)
{
    for(int i = 0; i <n; i ++)
    {
        points[i].parent = i;
        points[i].sz = 1;
    }
}
int find(int u)
{
    if(points[u].parent == u) return u;
    points[u].parent = find(points[u].parent);
    return points[u].parent;
}
void unite(int u, int v)
{
    u = find(u);
    v = find(v);
    if(u !=v)
    {
        if(points[u].sz > points[v].sz) swap(u, v);
        points[u].parent = v;
        points[v].sz +=points[u].sz;
    }
}

bool stage1 = true, none  = false;
int firstcycpar = -1;
vector<int> crit = {};
int cycles = 0;
int deg[1000006];
vector<int> specials;
vector<int>graph[1000006];
bool change = true;
bool valid = false;
bool visited[1000006];

void check_valid(int u, int erd, int par)
{
  visited[u] = true;
  for(auto v:graph[u])
  {
    if(v == erd)
    {
      continue;
    }
    if(visited[v] && v != par)
    {
      valid = false; //cout << v << " 1" << '\n'; 
      return;
    }
    if(!visited[v])
    {
      int d = 0;
      for(auto v1 : graph[v])
      {
        if (v1 != erd){d ++;}
      }
      if(d > 2)
      {
        valid = false; //cout << v << " 2" << '\n'; 
        return;
      }
      check_valid(v, erd, u);
    }
  }
  
}


void Init(int N_) 
{
  N = N_;
  construct(N);
  for(int i = 0; i <N; i ++)
  {
    crit.push_back(i);
  }
}

void Link(int A, int B) 
{
  graph[B].push_back(A);
  graph[A].push_back(B);
  if(stage1)
  {
    int a = find(A); int b = find(B);
    if( a == b)
    {
      if(cycles == 1 && a !=firstcycpar)
      {
        none = true; return;
      }
      else if(cycles == 0){ cycles ++; firstcycpar = a;}
    }
    else {unite(a, b);}
    a = find(A);  b = find(B);
    deg[A] ++; deg[B] ++;
    if(deg[A] >=3) 
    {
      if(cycles == 1 && firstcycpar!=a)
      {
        none = true; return;
      }
      if(cycles == 1 && firstcycpar == a)
      stage1 = false;
      specials.push_back(A);
      for(auto v: graph[A])
      {
        specials.push_back(v);
      }
    }
    else if(deg[B] >=3) 
    {
      if(cycles == 1 & firstcycpar!=b)
      {
        none = true; return;
      }
      stage1 = false;
      specials.push_back(B);
      for(auto v: graph[B])
      {
        specials.push_back(v);
      }
    }
  }
  else
  {
    int a = find(A); int b = find(B);
    if( a == b)
    {
      if(cycles == 1 && a!= firstcycpar)
      {
        none = true; return;
      }
      else if(cycles == 0 && a != find(specials[0]))
      {
        none = true; return;
      } 
      else{ cycles ++; firstcycpar = a;}
    }
    else {unite(a, b);}

    deg[A] ++; deg[B] ++;
    if(deg[A] == 4 || deg[B] == 4)
    {
      none = true; return;
    }

    if(deg[A] == 3)
    {
      for(int i = 0 ; i <specials.size(); i ++)
      {
        bool in = false;
        for(auto v : graph[A])
        {
          if(specials[i] == v){in = true;}
        }
        if(A == specials[i]){in = true;}
        if(!in){specials.erase(specials.begin() + i);}
      }
    }
    if(deg[A] == B)
    {
      for(int i = 0 ; i <specials.size(); i ++)
      {
        bool in = false;
        for(auto v : graph[B])
        {
          if(specials[i] == v){in = true;}
        }
        if(B== specials[i]){in = true;}
        if(!in){specials.erase(specials.begin() + i);}
      }
    }
    int c = find(specials[0]);
    if( a == c || b == c)
    {
      change = true;
    }
  }
}


int CountCritical() 
{
  if(none)
  {
    return 0;
  }
  if(stage1)
  {
    if(cycles == 0)
    {
      return N;
    }
    if(cycles == 1)
    {
      return points[firstcycpar].sz;
    }
  }
  // if there is one of degree 3:
  if(change)
  {
    for(int i = 0; i <specials.size(); i ++)
    {
      for(int j = 0 ; j <=N; j++)
      {
        visited[j] = false;
      }
      valid = true;
      //cout << "checking " << specials[i] << '\n';
      for(auto x : graph[specials[i]])
      {
        if(!visited[x])
          check_valid(x, specials[i], N);
      }
      if(!valid)
      {
        specials.erase(specials.begin() + i);
      }
    }
    change = false;
  }
  /*
   cout << '\n';
  for(auto s : specials)
  {
    cout << s << " ";
  }
  cout << '\n';
  */
  return specials.size();
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:126:17: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  126 |       if(cycles == 1 & firstcycpar!=b)
      |          ~~~~~~~^~~~
rings.cpp:163:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |       for(int i = 0 ; i <specials.size(); i ++)
      |                       ~~^~~~~~~~~~~~~~~~
rings.cpp:176:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |       for(int i = 0 ; i <specials.size(); i ++)
      |                       ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:216:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for(int i = 0; i <specials.size(); i ++)
      |                    ~~^~~~~~~~~~~~~~~~

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