제출 #589796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589796		daria	낙하산 고리들 (IOI12_rings)	C++14	52 / 100	1503 ms	262144 KiB

rings

#include "bits/stdc++.h"
using namespace std;
#define ll int
#define MAXN 1000005
#define _ << " " <<
//definizioni globali

vector<array<ll, 2> > edges;
ll ris=-1, stato = 0;
ll n;

struct grafo{
 ll par[MAXN], size[MAXN];
 vector<ll> adj[MAXN];
 ll can = -1, nc = 0, idx = -1;

 //union find
 ll find(ll a){
  if(par[a] == a) return a;
  return par[a]=find(par[a]);
 }

 bool same(ll a, ll b){
  return find(a) == find(b);
 }

 void unite(ll a, ll b){
  a = find(a);
  b = find(b);
  if(size[a] > size[b]) swap(a, b);
  par[a] = b;
  size[b] += size[a];
 }

 //archi
 void link(ll a, ll b){
  if(a == can || b == can) return;
  //cout << a _ b _ idx <<  " ";

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

  ll dega = adj[a].size(), degb = adj[b].size();
  bool check = 0;
  if(dega == 2 && degb == 2 && same(a, b)) check = 1; //creo un ciclo
  if(dega == 3 || degb ==  3) check = 1; //nodo con grado >= 3

  if(!same(a, b)) unite(a, b);

  if(check){
   if(idx == -1 || !same(idx, a)){
    nc++; idx = a;
   }
  }
  if(idx != -1) idx = find(idx);
  //cout << idx << endl;
 }

 //build
 void init(ll n){
  for(ll i=0; i<n; ++i){
   par[i] = i;
   size[i] = 1;
  }
  for(auto u : edges)
   link(u[0], u[1]);
 }

};


grafo G[5];

void Init(int N) {
 n = N;
 G[0].init(N);
}

void Link(int a, int b) {
 edges.push_back({a, b});
 grafo &g = G[0];
 g.link(a, b);
 for(ll i=0; i<n; ++i){
  //cout << i _ g.find(i) << endl;
 }
 ll dega = g.adj[a].size(), degb = g.adj[b].size();

 // aggiorno i 4 grafi alternativi
 if(stato == 1) for(ll i=1; i<5; ++i) G[i].link(a, b);

 //primo nodo con grado >= 3
 if(stato == 0){
  if(dega == 3){
   stato = 1;
   G[1].can = a; G[2].can = g.adj[a][0]; G[3].can = g.adj[a][1]; G[4].can = g.adj[a][2]; }
  else if(degb == 3){
   stato = 1;
   G[1].can = b; G[2].can = g.adj[b][0]; G[3].can = g.adj[b][1]; G[4].can = g.adj[b][2]; }

  // costruisco i 4 grafi alternativi
  if(stato == 1) for(ll i=1; i<5; ++i) G[i].init(n);
 }
}


int CountCritical() {
 if(ris == 0)
  return 0;

 grafo &g = G[0];

 //cout << endl <<  g.nc << " " << g.idx << endl;
 if(g.nc == 0)
  return n;

 if(g.nc >= 2)
  return ris = 0;

 //g.nc == 1
 if(stato == 0)
  return g.size[g.idx];

 //stato >= 1
 ll cnt =0;
 for(ll i= 1; i<5; ++i)
  cnt += (G[i].nc == 0);
 return ris = cnt;

}

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