제출 #575878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575878		arneves	낙하산 고리들 (IOI12_rings)	C++17	0 / 100	4086 ms	44104 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;

const int MX=1e6+5;
int n;
vector<int> adj[MX];
int visitados[MX];
int grau[MX];
vector<int> cand;
vector<int> grau3;
vector<int> grau4;

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

void Link(int A, int B){
	adj[A].push_back(B);
	adj[B].push_back(A);
	
	if(adj[A].size()==3){
		grau3.push_back(A);
		for(auto u: adj[A]) cand.push_back(u);
	}
	if(adj[B].size()==3){
		grau3.push_back(B);
		for(auto u: adj[B]) cand.push_back(u);
	}
	if(adj[A].size()==4){
		grau4.push_back(A);
	}
	if(adj[B].size()==4){
		grau4.push_back(B);
	}
}

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++) visitados[i]=0;
	for(int i=0; i<n; i++){
		if(i!=u && !visitados[i]){
			if(dfs(i,-1,u)){
				return 0;
			}
		}
	}
	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;
	}
	return 1;
}

int CountCritical(){
	if(grau4.size()>=2) return 0;
	if(grau4.size()==1) return f(grau4[0]);
	if(grau3.size()>=3) return 0;
	if(grau3.size()>0){
		int ans=0;
		for(auto u: grau3) if(f(u)) ans++;
		for(auto u: cand) if(f(u)) ans++;
		return ans;
	}
	
	int ans=0;
	for(int i=0; i<n; i++) if(f(i)) ans++;//, cout<<i<<" ";
	
	return ans;
}

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