Submission #917702

#	Time	Username	Problem	Language	Result	Execution time	Memory
917702		anton	Parachute rings (IOI12_rings)	C++17	20 / 100	4057 ms	65712 KiB

rings

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

#define int long long
#define pii pair<int, int>

int N;
vector<vector<int>> adj;
vector<bool> passed;
set<pii> m;
vector<int> oc;

vector<int> ending;


void Init(signed N_) {
  N = N_;
  oc.resize(5);
  adj.resize(N);
  ending.resize(N);
  passed.resize(N, false);
  set<int> l;
  for(int i= 0; i<N; i++){
    m.insert({0, i});
    oc[0]++;
  }
}
int flored(int id){
  return min(4LL, id);
}

void Link(signed A, signed B) {
  m.erase({adj[A].size(), A});
  m.erase({adj[B].size(), B});
  oc[flored(adj[A].size())]--;
  oc[flored(adj[B].size())]--;


  adj[A].push_back(B);
  adj[B].push_back(A);

  oc[flored(adj[A].size())]++;
  oc[flored(adj[B].size())]++;

  m.insert({adj[A].size(), A});
  m.insert({adj[B].size(), B});
}

int forbiden = 0;

bool dfs(int id, int anc){
  passed[id] = true;
  bool ok = true;
  for(auto v: adj[id]){
    if(v!=forbiden && v!=anc){
      if(passed[v]){
        return false;
      }
      else{
        ok &= dfs(v, id);
      }
    }
  }
  return ok;
}
bool test_crititcal(int id){
  forbiden = id;
  for(int i = 0; i<N; i++){  
    int deg =0;
    if(i == id){
      continue;
    }
    for(auto e: adj[i]){
      if(e!=id){
        deg++;
      }
    }
    if(deg>2){
      ////cout<<"deg "<<endl;
      return false;
    }
  }
  fill(passed.begin(), passed.end(), false);
  for(int i=  0; i<N; i++){
    if(!passed[i] && i!=forbiden){
      if(!dfs(i, -1)){
        ////cout<<"cycle "<<endl;
        return false;
      }
    }
  }
  return true;
}
int nbc = 0;

void nb_cycles(int u, int prev){
  passed[u] = true;
  for(auto v: adj[u]){
    if(v==prev){
      continue;
    }
    if(passed[v]){
      nbc++;
      //cout<<u<<" "<<v<<endl;
    }
    else{
      nb_cycles(v, u);
    }
  }
}
int find_intersection(int u, set<int>& res, int prev){
  passed[u] = true;
  int cur = 0;
  for(auto v: adj[u]){
    if(v==prev){
      continue;
    }
    if(passed[v]){
      ending[v] ++;
      cur++;
    }
    else{
      cur += find_intersection(v, res, u);
    }
  }
  cur-=ending[u];
  if(cur == nbc){
    res.insert(u);
  }
  return cur;
}
void find_ok_first(set<int>& ok){
  /*fill(passed.begin(), passed.end(), 0);
  nbc= 0;
  for(int i = 0; i<N; i++){
    if(!passed[i]){
      nb_cycles(i,-1);
    }
  }
  nbc/=2;
  //cout<<"nbc "<<nbc<<endl;

  fill(passed.begin(), passed.end(), 0);
  fill(ending.begin(), ending.end(), 0);
  for(int i = 0; i<N; i++){
    if(!passed[i]){
      find_intersection(i, ok, -1);
    }
  }*/

  for(int i = 0; i<N; i++){
    forbiden = i;
    fill(passed.begin(), passed.end(), false);
    bool maybe = true;
    for(int i=  0; i<N; i++){
      if(!passed[i] && i!=forbiden){
        if(!dfs(i, -1)){
          maybe = false;
        }
      }
    }
    if(maybe){
      ok.insert(i);
    }
  }
}
signed CountCritical() {
  int res= 0;
  if(oc[4]>1){
    return 0;
  }
  else if(oc[4] == 1){
    int cand = m.lower_bound({4, 0})->second;
    if(test_crititcal(cand)){
      res++;
    }
    return res;
  }
  else{
    set<int> ok;

    find_ok_first(ok);
    
    if(oc[3]>0){
      auto it = m.lower_bound({3, 0});
      for(; it!=m.end(); ++it){
        set<int> neigs;
        for(auto e: adj[it->second]){
          neigs.insert(e);
        }
        neigs.insert(it->second);
        vector<int> rem;
        for(auto e: neigs){
          if(ok.find(e) == ok.end()){
            rem.push_back(e);
          }
        }
        for(auto e: rem){
          neigs.erase(e);
        }
        swap(ok, neigs);
      }
    }
    return ok.size();
  }

}

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