Submission #1012772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012772		Ludissey	Parachute rings (IOI12_rings)	C++14	0 / 100	751 ms	151680 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
int n;
bool hasloop=false;
vector<vector<int>> neigh;
vector<int> critC;
vector<int> crit;
vector<int> low;
vector<int> tin;
vector<int> visited;
vector<int> critCOUNT;
int timer=0;
int exceptation=-1;


void detect_cycle(int x, int p) {
  visited[x]=true;
  low[x]=tin[x]=timer++;
  for (int to : neigh[x]) {
    if (to == p ||to==exceptation) continue;
    if (visited[to]) {
      low[x] = min(low[x], tin[to]);
    } else {
        detect_cycle(to, x);
        low[x] = min(low[x], low[to]);
    }
  }
}

void Init(signed N_) {
  n = N_;
  neigh.resize(N_);
  critC.resize(N_);
  crit.resize(N_);
  critCOUNT.resize(N_);
  visited.resize(n,0);
  tin.resize(n,0);
  low.resize(n,0);
}

void Link(signed A, signed B) {
  neigh[A].push_back(B);
  neigh[B].push_back(A);
}

signed CountCritical() {
  int c=0;
  for (int i = 0; i < n; i++)
  {
    visited[i]=0;
    tin[i]=0;
    low[i]=0;
    critC[i]=0;
    crit[i]=0;
    critCOUNT[i]=0;
  }
  timer=0;
  for (int i = 0; i < n; i++) if(!visited[i]) detect_cycle(i,-1);
  vector<int> mp(n,0);
  int cyc=0;
  int cyl=-1;
  int mx=0;
  int center=-1;
  exceptation=-1;
  for (int i = 0; i < n; i++) {
    if(sz(neigh[i])==3) {
      critCOUNT[i]++;
      critCOUNT[neigh[i][0]]++;
      critCOUNT[neigh[i][1]]++;
      critCOUNT[neigh[i][2]]++;
      mx++;
    }else if(sz(neigh[i])>=4) {
      critCOUNT[i]++;
      center=i;
      mx++;
    }
  }
  for (int i = 0; i < n; i++){
    mp[low[i]]++;
    if(mp[low[i]]==3) {
      cyc++;
      cyl=low[i];
    }
  }
  if(cyc>=2) {
    exceptation=center;
    for (int i = 0; i < n; i++) if(!visited[i]) detect_cycle(i,-1);\
    cyc=0;
    for (int i = 0; i < n; i++){
      mp[low[i]]++;
      if(mp[low[i]]==3) {
        cyc++;
        cyl=low[i];
      }
    }
    if(cyc==0) return 1;
    else return 0;
  }
  for (int i = 0; i < n; i++) {
    if(cyc==0) critC[i]=true;
    else if(low[i]==cyl) critC[i]=true;
    else critC[i]=false;
  }
  for (int i = 0; i < n; i++){
    if(critCOUNT[i]==mx&&critC[i]==true) crit[i]=true;
  }
  for (int i = 0; i < n; i++) { if(crit[i]) c++; }
  return c;
}

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