제출 #1239425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239425		guanex	Parachute rings (IOI12_rings)	C++20	0 / 100	313 ms	55208 KiB

rings

#include<bits/stdc++.h>

using namespace std;

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

void Init(int N_) {
  for(int i = 0; i <= N_; ++i){
    f[i] = i;
    //cout << "init " << i << " " << f[i] << endl;
    len[i] = 1;
  }
  N = N_;
}

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(ed[A].size() == 4){
    solvable = 0;
  }
  if(ed[B].size() == 4){
    solvable = 0;
  }
  if(triple){
    unordered_map<int, int> m;
    int need = 1;
    for(auto e:possibles){
      m[e]++;
    }
    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(ed[A].size() == 3 || ed[B].size() == 3){
    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)]);
  }
}

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

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(triple){
    int ans = 0;
    for(auto e:possibles){
      //cout << e <<  " ";
      ans += check(e);
    }
    //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: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31