제출 #575892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575892		arneves	낙하산 고리들 (IOI12_rings)	C++17	55 / 100	4056 ms	94712 KiB

rings

/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
	       .      .           .      .           .      .    	
	       _\/  \/_           _\/  \/_           _\/  \/_    	
	        _\/\/_             _\/\/_             _\/\/_     	
	    _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
	     / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
	        _/\/\_             _/\/\_             _/\/\_     	
	        /\  /\             /\  /\             /\  /\     	
	       '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
 
using namespace std;
typedef long long ll;

class DSU //with range compression and union by subtree size
{
	public:
	ll N;
	vector<ll> p,siz;
	
	DSU(ll n)
	{
		N=n; for(int i=0; i<N; i++){p.push_back(i); siz.push_back(1);}
	}
	
	ll find(ll x)
	{
		if(p[x]==x) {return x;}
		ll ans=find(p[x]);
		p[x]=ans; 
		return ans;
	}
	
	void unionn(ll a, ll b)
	{
		a=find(a); b=find(b);
		if(a==b) {return;}
		if(siz[a]>siz[b]) {swap(a,b);}
		p[a]=b; siz[b]+=siz[a];
	}
};

const int MX=1e6+5;
int n;
vector<int> adj[MX];
int visitados[MX];
int grau[MX];
int ciclos=0;
vector<int> gajos_no_ciclo;
vector<int> cand;
vector<int> grau3;
vector<int> grau4;
DSU dsu(MX);

int last=-1;
int ready=0;

void Init(int N){
	n=N;
	for(int i=0; i<n; i++) grau[i]=0;
}

int dfs2(int s, int p, int t){
	int ans=0;
	for(auto u: adj[s]){
		if(u!=p){
			if(u==t){
				ans++;
			}else{
				ans+=dfs2(u,s,t);
			}
		}
	}
	if(ans){
		gajos_no_ciclo.push_back(s);
		return 1;
	}else{
		return 0;
	}
}

void Link(int A, int B){
	adj[A].push_back(B);
	adj[B].push_back(A);
	grau[A]++;
	grau[B]++;
	if(dsu.find(A)==dsu.find(B)){
		if(ciclos==0){
			dfs2(A,-1,B);
			gajos_no_ciclo.push_back(B);
		}
		ciclos++;
	}
	
	dsu.unionn(A,B);
	
	if(grau[A]==3){
		grau3.push_back(A);
		for(auto u: adj[A]) cand.push_back(u);
	}
	if(grau[B]==3){
		grau3.push_back(B);
		for(auto u: adj[B]) cand.push_back(u);
	}
	if(grau[A]==4){
		grau4.push_back(A);
	}
	if(grau[B]==4){
		grau4.push_back(B);
	}
	ready=0;
}

int dfs(int s, int p, int pro){
	visitados[s]=1;
	int ans=0;
	for(auto u: adj[s]){
		if(u!=p && u!=s && u!=pro){
			if(visitados[u]) return 1;
			else ans+=dfs(u,s,pro);
		}
	}
	return ans>0;
}

int f(int u){
	for(int i=0; i<n; i++){
		if(i==u) continue;
		vector<int> v;
		for(auto y: adj[i]) if(y!=u) v.push_back(y);
		if(v.size()>2) return 0;
	}
	for(int i=0; i<n; i++) visitados[i]=0;
	for(int i=0; i<n; i++){
		if(i!=u && !visitados[i]){
			if(dfs(i,-1,u)){
				return 0;
			}
		}
	}
	return 1;
}

int CountCritical(){
	if(last==0 || ready==1) return last;
	ready=1;
	if(grau4.size()>=2) return last=0;
	if(grau4.size()==1) return last=f(grau4[0]);
	if(grau3.size()>=5) return last=0;
	if(grau3.size()>0){
		int ans=0;
		set<int> s;
		for(auto u: cand) s.insert(u);
		for(auto u: grau3) s.insert(u); 
		for(auto u: s) if(f(u)) ans++;
		last=ans;
		return ans;
	}
	if(ciclos>=2){
		return last=0;
	}
	if(ciclos==1){
		return last=gajos_no_ciclo.size();
	}
	
	/*int ans=0;
	for(int i=0; i<n; i++) if(f(i)) ans++;//, cout<<i<<" ";*/
	last=n;
	return n;
}

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