제출 #120092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120092		nvmdava	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	3608 ms	248560 KiB

rings

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

int N;
int p[1000005];
int cyc = 0;
set<int> adj[1000005];
set<int> pos, t;
int find(int v){
   if(v == p[v]) return v;
   return p[v] = find(p[v]);
}
bool merge(int v, int u){
   v = find(v);
   u = find(u);
   if(v == u) return 1;
   p[v] = u;
   return 0;
}
void Init(int N_) {
   N = N_;
   for(int i = 0; i < N; i++){
      p[i] = i;
      pos.insert(i);
   }
}
bool in[1000005];
int lol, q;
int dfs(int v){
   if(pos.count(v))
      t.insert(v);
   if(lol != v && adj[v].count(q)){
      return 1;
   }
   for(int x : adj[v]){
      if(!in[x]){
         in[x] = 1;
         if(dfs(x) == 1) return 1;
      }
   }
   if(t.count(v))
      t.erase(v);
   return 0;
}

void Link(int v, int u) {
   if(pos.empty()) return;
   adj[v].insert(u);
   adj[u].insert(v);
   if(adj[v].size() > 3){
      if(pos.count(v)){
         pos = {v};
      } else {
         pos.clear();
      }
   } else if(adj[v].size() == 3){
      for(int x : adj[v]){
         if(pos.count(x)) t.insert(x);
      }
      if(pos.count(v)) t.insert(v);
      swap(pos, t);
      t.clear();
   }
   if(adj[u].size() > 3){
      if(pos.count(u)){
         pos = {u};
      } else {
         pos.clear();
      }
   } else if(adj[u].size() == 3){
      for(int x : adj[u]){
         if(pos.count(x)) t.insert(x);
      }
      if(pos.count(u)) t.insert(u);
      swap(pos, t);
      t.clear();
   }
   if(merge(v, u) == 0) return;
   cyc++;
   if(cyc >= 3){
      pos.clear();
      return;
   }
   memset(in, 0, sizeof in);
   if(pos.count(v))
      t.insert(v);
   if(pos.count(u))
      t.insert(u);
   lol = u;
   q = v;
   in[v] = 1;
   in[u] = 1;
   dfs(u);
   swap(t, pos);
   t.clear();
}

int CountCritical() {
  return pos.size();
}

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