oj.uz

Submission #255695

# Submission time Handle Problem Language Result Execution time Memory
255695 2020-08-01T15:26:35 Z tincamatei Parachute rings (IOI12_rings) C++14
37 / 100
 1552 ms 219592 KB 
#include <bits/stdc++.h>

const int MAX_N = 1000000;

struct DSU {
  int N;
  int sef[MAX_N], grad[MAX_N], rank[MAX_N], size[MAX_N];
  bool ignore[MAX_N];

  enum ProblemState {
    ONLY_CYCLES,    // Am doar lanturi sau ciclii, tb doar sa vedem daca avem un singur ciclu
    CRITICAL_NODES, // Am noduri de grade mai mari sau egale cu 3
                    // vedem ce se intampla daca excludem cate un nod critic, sa nu avem cicluri
                    // sau alte noduri cu grad mai mare ca 3
    NOTHING         // Raspunsul va fi 0 pentru totdeauna
  } state;

  int sizeCycle, cntCycle, gg3;

  std::vector<std::pair<int*, int> > history;
  std::vector<int> criticalNodes;
  std::vector<std::pair<int, int> > edges;
  std::vector<int> graph[MAX_N];

  void setSize(int _N) {
    state = ONLY_CYCLES;
    N = _N;
    reset();
  }

  void reset() {
    for(int i = 0; i < N; ++i) {
      sef[i] = i;
      grad[i] = 0;
      rank[i] = 0;
      size[i] = 1;
    }
    sizeCycle = cntCycle = gg3 = 0;
  }

  int myfind(int x) {
    if(sef[x] == x)
      return x;
    return myfind(sef[x]);
  }

  void initOnlyCyclesState(int firstCritical) {
    criticalNodes.push_back(firstCritical);
    ignore[firstCritical] = true;
    for(auto it: graph[firstCritical]) {
      criticalNodes.push_back(it);
      ignore[it] = true;
    }
    
    reset();
    
    state = CRITICAL_NODES;
    for(auto it: edges)
      link(it.first, it.second);
  }

  void addEdge(int a, int b) {
    edges.push_back(std::make_pair(a, b));
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  void persistentModify(int* x, int y) {
    history.push_back(std::make_pair(x, *x));
    *x = y;
  }

  void link(int a, int b) {
    int sa, sb;
  
    sa = myfind(a);
    sb = myfind(b);
    if(rank[sa] < rank[sb]) {
      std::swap(a, b);
      std::swap(sa, sb);
    }
    
    if(!ignore[a] && !ignore[b]) {
      if(state == ONLY_CYCLES) {
        grad[a]++;
        grad[b]++;
        if(grad[a] > 2)
          initOnlyCyclesState(a);
        else if(grad[b] > 2)
          initOnlyCyclesState(b);
        else if(sa == sb) {
          cntCycle++;
          sizeCycle = size[sa];

          if(cntCycle > 1)
            state = NOTHING;
        } else {
          sef[sb] = sa;
          rank[sa] = rank[sa] + (rank[sa] == rank[sb]);
          size[sa] = size[sb] + size[sa];
        }
      } else if(state == CRITICAL_NODES) {
        persistentModify(&grad[a], grad[a] + 1);
        persistentModify(&grad[b], grad[b] + 1);
        if(sa == sb)
          persistentModify(&cntCycle, cntCycle + 1);
        else {
          persistentModify(&sef[sb], sa);
          persistentModify(&rank[sa], rank[sa] + (rank[sa] == rank[sb]));
          persistentModify(&size[sa], size[sb] + size[sa]);
        }

        if(grad[a] > 2)
          persistentModify(&gg3, gg3 + 1);
        if(grad[b] > 2)
          persistentModify(&gg3, gg3 + 1);
      }
    }
  }

  int getTimeStamp() {
    return history.size();
  }

  void revertTimestamp(int timestamp) {
    while(history.size() > timestamp) {
      *history.back().first = history.back().second;
      history.pop_back();
    }
  }

  void sanitizeCritical() {
    std::vector<int> sanitized;
    std::vector<int> badNodes;
    std::vector<std::pair<int, int> > addedEdges;

    for(int i = 0; i < criticalNodes.size(); ++i) {
      addedEdges.clear();

      int ts = getTimeStamp();
      for(int j = 0; j < criticalNodes.size(); ++j)
        if(i != j)
          ignore[criticalNodes[j]] = false;
      for(int j = 0; j < criticalNodes.size(); ++j)
        if(i != j)
          for(auto it: graph[criticalNodes[j]]) {
            bool ok = true;
            for(auto edge: addedEdges)
              if(edge == std::make_pair(criticalNodes[j], it) ||
                 edge == std::make_pair(it, criticalNodes[j]))
                ok = false;
            if(ok) {
              link(criticalNodes[j], it);
              addedEdges.push_back(std::make_pair(it, criticalNodes[j]));
            }
          }
      if(gg3 == 0 && cntCycle == 0)
        sanitized.push_back(criticalNodes[i]);
      else
        badNodes.push_back(criticalNodes[i]);

      for(int j = 0; j < criticalNodes.size(); ++j) 
        if(i != j)
          ignore[criticalNodes[j]] = true;
      revertTimestamp(ts);
    }
    
    criticalNodes = sanitized;
    for(auto it: badNodes)
      ignore[it] = false;

    addedEdges.clear();
    for(auto it: badNodes)
      for(auto it2: graph[it]) {
        bool ok = false;
        for(auto edge: addedEdges)
          if(edge == std::make_pair(it, it2) ||
             edge == std::make_pair(it2, it))
            ok = false;
        if(ok) {
          link(it, it2);
          addedEdges.push_back(std::make_pair(it, it2));
        }
      }

    if(criticalNodes.size() == 0)
      state = NOTHING;
  }

  int getCriticalPoints() {
    switch(state) {
    case ONLY_CYCLES:
      if(cntCycle == 0)
        return N;
      else if(cntCycle == 1)
        return sizeCycle;
      else
        return 0;
    case CRITICAL_NODES:
      sanitizeCritical();
      return criticalNodes.size();
    case NOTHING:
      return 0;
    }
    return 0;
  }
} dsu;

void Init(int N_) {
  dsu.setSize(N_);
}

void Link(int A, int B) {
  dsu.addEdge(A, B);
  dsu.link(A, B);
}

int CountCritical() {
  int res = dsu.getCriticalPoints();
  return res;
}

Compilation message

rings.cpp: In member function 'void DSU::revertTimestamp(int)':
rings.cpp:126:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(history.size() > timestamp) {
           ~~~~~~~~~~~~~~~^~~~~~~~~~~
rings.cpp: In member function 'void DSU::sanitizeCritical()':
rings.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < criticalNodes.size(); ++i) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~
rings.cpp:141:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < criticalNodes.size(); ++j)
                      ~~^~~~~~~~~~~~~~~~~~~~~~
rings.cpp:144:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < criticalNodes.size(); ++j)
                      ~~^~~~~~~~~~~~~~~~~~~~~~
rings.cpp:162:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < criticalNodes.size(); ++j) 
                      ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 18 ms 24712 KB Output is correct
3 Correct 18 ms 24700 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 15 ms 24064 KB Output is correct
8 Correct 16 ms 24064 KB Output is correct
9 Correct 18 ms 24828 KB Output is correct
10 Correct 18 ms 24828 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 59356 KB Output is correct
2 Correct 1225 ms 140928 KB Output is correct
3 Correct 1439 ms 213480 KB Output is correct
4 Correct 1286 ms 92120 KB Output is correct
5 Correct 1325 ms 92260 KB Output is correct
6 Correct 1269 ms 90452 KB Output is correct
7 Correct 1373 ms 213376 KB Output is correct
8 Correct 1421 ms 217068 KB Output is correct
9 Correct 1552 ms 219592 KB Output is correct
10 Correct 883 ms 89044 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 18 ms 24712 KB Output is correct
3 Correct 18 ms 24700 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 15 ms 24064 KB Output is correct
8 Correct 16 ms 24064 KB Output is correct
9 Correct 18 ms 24828 KB Output is correct
10 Correct 18 ms 24828 KB Output is correct
11 Correct 20 ms 24840 KB Output is correct
12 Correct 21 ms 25720 KB Output is correct
13 Incorrect 22 ms 25596 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 18 ms 24712 KB Output is correct
3 Correct 18 ms 24700 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 15 ms 24064 KB Output is correct
8 Correct 16 ms 24064 KB Output is correct
9 Correct 18 ms 24828 KB Output is correct
10 Correct 18 ms 24828 KB Output is correct
11 Correct 20 ms 24840 KB Output is correct
12 Correct 21 ms 25720 KB Output is correct
13 Incorrect 22 ms 25596 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 18 ms 24712 KB Output is correct
3 Correct 18 ms 24700 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 15 ms 24064 KB Output is correct
8 Correct 16 ms 24064 KB Output is correct
9 Correct 18 ms 24828 KB Output is correct
10 Correct 18 ms 24828 KB Output is correct
11 Correct 510 ms 59356 KB Output is correct
12 Correct 1225 ms 140928 KB Output is correct
13 Correct 1439 ms 213480 KB Output is correct
14 Correct 1286 ms 92120 KB Output is correct
15 Correct 1325 ms 92260 KB Output is correct
16 Correct 1269 ms 90452 KB Output is correct
17 Correct 1373 ms 213376 KB Output is correct
18 Correct 1421 ms 217068 KB Output is correct
19 Correct 1552 ms 219592 KB Output is correct
20 Correct 883 ms 89044 KB Output is correct
21 Correct 20 ms 24840 KB Output is correct
22 Correct 21 ms 25720 KB Output is correct
23 Incorrect 22 ms 25596 KB Output isn't correct
24 Halted 0 ms 0 KB -