oj.uz

Submission #169257

# Submission time Handle Problem Language Result Execution time Memory
169257 2019-12-19T10:05:29 Z AlexLuchianov Parachute rings (IOI12_rings) C++14
20 / 100
 14 ms 7800 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

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());
  //assert(candidates.size() < 6);
  vector<int> newcand;
  for(int i = 0; i < candidates.size(); i++)
    if(test(candidates[i]) == 1)
      newcand.push_back(candidates[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

rings.cpp: In function 'void dfs(int, int, bool&, int)':
rings.cpp:50: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:74: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 computecandidates()':
rings.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < candidates.size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:130:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[a].size(); h++)
                      ~~^~~~~~~~~~~~~
rings.cpp:132:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[b].size(); h++)
                      ~~^~~~~~~~~~~~~
rings.cpp:139:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[a].size(); h++)
                    ~~^~~~~~~~~~~~~
rings.cpp:141:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[b].size(); h++)
                    ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 7 ms 2936 KB Output is correct
10 Correct 7 ms 2936 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 7800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 7 ms 2936 KB Output is correct
10 Correct 7 ms 2936 KB Output is correct
11 Correct 8 ms 3064 KB Output is correct
12 Correct 13 ms 3192 KB Output is correct
13 Incorrect 14 ms 3324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 7 ms 2936 KB Output is correct
10 Correct 7 ms 2936 KB Output is correct
11 Correct 8 ms 3064 KB Output is correct
12 Correct 13 ms 3192 KB Output is correct
13 Incorrect 14 ms 3324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 4 ms 2808 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 7 ms 2936 KB Output is correct
10 Correct 7 ms 2936 KB Output is correct
11 Runtime error 10 ms 7800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -