Submission #917735

#	Time	Username	Problem	Language	Result	Execution time	Memory
917735		anton	Parachute rings (IOI12_rings)	C++17	55 / 100	4051 ms	167020 KiB

rings

#include<bits/stdc++.h>
#pragma("03")
using namespace std;

#define pii pair<int, int>

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



void Init(signed N_) {
  N = N_;
  oc.resize(5);
  adj.resize(N);
  passed.resize(N, false);
  for(int i= 0; i<N; i++){
    m.insert({0, i});
    oc[0]++;
  }
}
int flored(int id){
  return min(4, 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[B].size(), B});
}

int forbiden = 0;
bool acyclic = true;

void dfs(int id, int anc){
  passed[id] = true;
  for(auto v: adj[id]){
    if(v!=forbiden && v!=anc){
      if(passed[v]){
        acyclic = false;
      }
      else{
        dfs(v, id);
      }
    }
  }
}
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);
  acyclic = true;
  for(int i=  0; i<N; i++){
    if(!passed[i] && i!=forbiden){
      dfs(i, -1);
    }
  }
  return acyclic;
}
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);
    }
  }
}
pair<bool, int> find_single(int u, int a, set<int>& s){
  passed[u] = true;
  for(auto v: adj[u]){
    if(v!=a){
      if(passed[v]){
        s.insert(u);
        return {true, v};
      }
      else{
        auto res = find_single(v, u, s);
        if(res.second == u){
          s.insert(u);
          return {false, -1};
        }
        else{
          if(res.first){
            s.insert(u);
            return res;
          }
        }
      }
    }
  }
  return {false, -1};
}
void calc_cycles(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;
}
void find_ok_first(set<int>& ok){
  
  
  /*cout<<"ok "<<endl;
  for(auto e: ok){
    cout<<e<<" ";
  }
  cout<<endl;*/
}
signed CountCritical() {

  m.clear();
  for(int i = 0; i<N; i++){
    m.insert({adj[i].size(), i});
  }
  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;

    calc_cycles(ok);
    if(nbc==1){
      fill(passed.begin(), passed.end(), 0);
      for(int i = 0; i<N; i++){
        if(!passed[i]){
          find_single(i,-1, ok);
        }
      }
    }
    if(oc[3]>0){
      auto it = m.lower_bound({3, 0});
      vector<int> off(N);
      for(; it!=m.end(); ++it){
        set<int> neigs;
        for(auto e: adj[it->second]){
          off[e]++;
        }
        off[it->second]++;
      }
      set<int> pass;
      for(int i = 0; i<N; i++){
        if(off[i] == oc[3]){
          if(test_crititcal(i)){
            pass.insert(i);
          }
        }
      }
      return pass.size();
    }
    else if(nbc==0){
      return N;
    }
    
    return ok.size();
  }

}

Compilation message (stderr)

rings.cpp:2: warning: ignoring '#pragma ( ' [-Wunknown-pragmas]
    2 | #pragma("03")
      |

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