Submission #917670

#	Time	Username	Problem	Language	Result	Execution time	Memory
917670		anton	Parachute rings (IOI12_rings)	C++17	20 / 100	4037 ms	68396 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;


void Init(signed N_) {
  N = N_;
  adj.resize(N);
  passed.resize(N, false);
  set<int> l;
  for(int i= 0; i<N; i++){
    m.insert({0, i});
  }
}

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

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

  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;
}
signed CountCritical() {

  int res= 0;
 for(int i = 0; i<N; i++){
  if(test_crititcal(i)){
    //cout<<i<<" ";
    res++;
  }
 }
 return res;

}

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