Submission #1149236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149236		julia_08	Parachute rings (IOI12_rings)	C++20	55 / 100	4091 ms	107812 KiB

rings

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

const int MAXN = 1e6 + 10;

int deg[MAXN], marc[MAXN], cur_deg[MAXN], saiu[MAXN];

vector<int> adj[MAXN];

int n;

void Init(int n_){

  n = n_;

  for(int i=0; i<n; i++){
    adj[i].clear();
    deg[i] = 0;
  }

}

void Link(int a, int b){

  adj[a].push_back(b);
  adj[b].push_back(a);

  deg[a] ++, deg[b] ++;

}

bool ciclo = false;

int cur_sz;

void dfs(int v, int p, int x){

  marc[v] = 1;
  cur_sz ++;

  for(auto u : adj[v]){
    if(!marc[u] && u != x){
      dfs(u, v, x);

    } else if(u != p && marc[u] && !saiu[u] && u != x){
      ciclo = true;
    }
  }

  saiu[v] = 1;
}

int CountCritical(){

  for(int i=0; i<n; i++){
    marc[i] = saiu[i] = 0;
  }

  for(int i=0; i<n; i++){
    cur_deg[i] = deg[i];
  }

  pair<int, int> max_deg = {-1, -1};

  for(int i=0; i<n; i++){
    if(cur_deg[i] > max_deg.first){
      max_deg = {cur_deg[i], i};
    }
  }

  if(max_deg.first < 3){
    // so me importo com ciclos:

    int cnt_ciclos = 0;

    int sz = 0;

    for(int i=0; i<n; i++){
      if(!marc[i]){
        ciclo = false;
        cur_sz = 0;
        dfs(i, i, -1);
        if(ciclo){
          sz = cur_sz;
          cnt_ciclos ++;
        }
      }
    }

    if(cnt_ciclos > 1){
      // tem mais de uma componente com ciclos
      return 0;
    }

    if(cnt_ciclos == 0) return n;

    return sz;
  }

  vector<int> v = {max_deg.second};

  if(max_deg.first <= 3) for(auto j : adj[max_deg.second]) v.push_back(j);

  int ans = 0;

  for(auto x : v){

    for(int i=0; i<n; i++) cur_deg[i] = deg[i], marc[i] = saiu[i] = 0;

    cur_deg[x] = 0;

    for(auto j : adj[x]){
      cur_deg[j] --;
    }

    bool ok = true;

    for(int i=0; i<n; i++){
      if(!marc[i] && i != x){
        ciclo = false;
        dfs(i, i, x);
        if(ciclo) ok = false;
      }
    }

    for(int i=0; i<n; i++){
      if(cur_deg[i] > 2){
        ok = false;
      }
    }

    if(ok) ans ++;

  }

  return ans;
}

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