oj.uz

Submission #169255

# Submission time Handle Problem Language Result Execution time Memory
169255 2019-12-19T09:54:57 Z AlexLuchianov Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 7800 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 909 ms 2936 KB Output is correct
3 Correct 449 ms 2936 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2860 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 335 ms 2808 KB Output is correct
8 Correct 417 ms 3032 KB Output is correct
9 Correct 974 ms 3068 KB Output is correct
10 Correct 1310 ms 3116 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 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 909 ms 2936 KB Output is correct
3 Correct 449 ms 2936 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2860 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 335 ms 2808 KB Output is correct
8 Correct 417 ms 3032 KB Output is correct
9 Correct 974 ms 3068 KB Output is correct
10 Correct 1310 ms 3116 KB Output is correct
11 Correct 2258 ms 3264 KB Output is correct
12 Execution timed out 4041 ms 3320 KB Time limit exceeded
13 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 909 ms 2936 KB Output is correct
3 Correct 449 ms 2936 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2860 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 335 ms 2808 KB Output is correct
8 Correct 417 ms 3032 KB Output is correct
9 Correct 974 ms 3068 KB Output is correct
10 Correct 1310 ms 3116 KB Output is correct
11 Correct 2258 ms 3264 KB Output is correct
12 Execution timed out 4041 ms 3320 KB Time limit exceeded
13 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 909 ms 2936 KB Output is correct
3 Correct 449 ms 2936 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2860 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 335 ms 2808 KB Output is correct
8 Correct 417 ms 3032 KB Output is correct
9 Correct 974 ms 3068 KB Output is correct
10 Correct 1310 ms 3116 KB Output is correct
11 Runtime error 11 ms 7800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -