제출 #1239439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239439		guanex	낙하산 고리들 (IOI12_rings)	C++20	37 / 100	775 ms	67808 KiB

rings

#include<bits/stdc++.h>

using namespace std;

int N;
vector<vector<int>> ed(1000005, (vector<int>){});
vector<int> cycles;
vector<int> possibles;
int solvable = 2;
bool triple = 0;
int f[1000005];
int len[1000005];

void Init(int N_) {
    N = N_;
    triple = false;
    solvable = 2;
    cycles.clear();
    possibles.clear();
    for(int i = 0; i <= N_; ++i){
        ed[i].clear();
        f[i] = i;
        len[i] = 1;
    }
}

int ffather(int no){
  //cout << "check " << no << " " << f[no] << endl;
  if(f[no] == no){
    return no;
  }
  return f[no] = ffather(f[no]);
}

bool join(int u, int v){
  u = ffather(u);
  v = ffather(v);
  if(u == v){
    return 0;
  }
  if(len[v] > len[u]){
    swap(u, v);
  }
  len[u] += len[v];
  f[v] = u;
  return 1;
}

void Link(int A, int B) {
  ed[A].push_back(B);
  ed[B].push_back(A);
  if(solvable == 0){return;}
  if((int)ed[A].size() == 4){
    solvable--;
    possibles = {A};
  }
  if((int)ed[B].size() == 4){
    solvable--;
    possibles = {B};
  }
  bool three = 0;
  if((int)ed[B].size() == 3){
    three = 1;
  }
  if((int)ed[A].size() == 3){
    three = 1;
  }
  if(triple && three){
    unordered_map<int, int> m;
    int need = 1;
    for(auto e:possibles){
      m[e]++;
    }
    if((int)ed[A].size() == 3){
      need++;
      m[A]++;
      for(auto e:ed[A]){
        m[e]++;
      }
    }
    if((int)ed[B].size() == 3){
      need++;
      m[B]++;
      for(auto e:ed[B]){
        m[e]++;
      }
    }
    possibles.clear();
    for(auto e:m){
      if(e.second == need){
        possibles.push_back(e.first);
      }
    }
    if(!join(A, B)){
      cycles.push_back(len[ffather(A)]);
      return;
    }
    return;
  }
  if(three){
    triple = 1;
    unordered_map<int, int> m;
    int need = 0;
    if(ed[A].size() == 3){
      need++;
      m[A]++;
      for(auto e:ed[A]){
        m[e]++;
      }
    }
    if(ed[B].size() == 3){
      need++;
      m[B]++;
      for(auto e:ed[B]){
        m[e]++;
      }
    }
    possibles.clear();
    for(auto e:m){
      if(e.second == need){
        possibles.push_back(e.first);
      }
    }
    return;
  }
  if(!join(A, B)){
    cycles.push_back(len[ffather(A)]);
    return;
  }
}

bool dfs(int no, int fat, int ex, vector<int> &vis){
  if(no == ex){
    return 1;
  }
  vis[no] = 1;
  for(auto e:ed[no]){
    if(e == fat)continue;
    if(e == ex)continue;
    if(vis[e] == 1){
      return 0;
    }
    if(dfs(e, no, ex, vis) == 0){
      return 0;
    }
  }
  return 1;
}

bool check(int exclude){
  vector<int> vis(1000005, 0);
  bool ans = 1;
  for(int i = 0; i < N; ++i){
    if(!vis[i]){
      ans &= dfs(i, -1, exclude, vis);
    }
  }
  return ans;
}

int CountCritical() {
  if(!solvable){
    return 0;
  }
  if(solvable == 1){
    int ans = check(possibles[0]);
    return ans;
  }
  if(triple){
    int ans = 0;
    for(auto e:possibles){
      //cout << e <<  " ";
      if(check(e)){
        ans++;
      }
    }
    //cout << endl;
    return ans;
  }else{
    if((int)cycles.size() == 0){
      return N;
    }else if((int)cycles.size() == 1){
      return cycles[0];
    }else{
      return 0;
    }
  }
  return -1e9;
}

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