제출 #1153102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153102		enzy	낙하산 고리들 (IOI12_rings)	C++20	0 / 100	4093 ms	44212 KiB

rings

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
vector<int>v[maxn];
int marc[maxn], n, grau[maxn];
bool ok;
void dfs(int u, int vim, int tirei){
	marc[u]++;
	for(int viz : v[u]){
		if(viz==vim||viz==tirei) continue;
		if(marc[viz]){
			ok=false;
			continue;
		}
		dfs(viz,u,tirei);
	}
}

void Init(int N_){
    n = N_;
    for(int i=0;i<n;i++) v[i].clear();
}

void Link(int a, int b){
    v[a].push_back(b);
    v[b].push_back(a);
}

int CountCritical(){
	int resp=0;
	for(int i=1;i<=n;i++) grau[i]=v[i].size();
	for(int i=1;i<=n;i++){
		grau[i]=0; // tirando o cara i
		for(int viz : v[i]) grau[viz]--; // tirando suas arestas
		bool pd=true;
		for(int j=1;j<=n;j++){
			if(grau[j]>=3) pd=false; // se tiver algm com grau >=3 acabou
			marc[j]=0;
		}
		if(pd){
			ok=true;
			for(int j=1;j<=n;j++) if(!marc[j]&&j!=i) dfs(j,i,i); // fznd a dfs pra ver se encontra ciclo
			if(ok) resp++;
		}
		// recolocando o cara i
		for(int viz : v[i]) grau[viz]++;
		grau[i]=v[i].size();
	}
	return resp;
}

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