제출 #255695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255695		tincamatei	낙하산 고리들 (IOI12_rings)	C++14	37 / 100	1552 ms	219592 KiB

rings

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31