제출 #1150760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150760		ChuanChen	낙하산 고리들 (IOI12_rings)	C++20	100 / 100	712 ms	121708 KiB

rings

#include<bits/stdc++.h>
using namespace std;
const int lim = 1e6+5;

struct UF{
	int N;
	int pai[lim], qtd_vert[lim], deg[lim];
	int circle_sz;
	bool sub;

	UF(){
		circle_sz = 0;
		for(int i = 0; i < lim; i++){
			pai[i] = i;
			qtd_vert[i] = 1;
			deg[i] = 0;
		}
	}

	int CRings(){
		if(sub) return circle_sz==0;
		if(circle_sz == 0) return N;
		if(circle_sz == -1) return 0;
		return circle_sz;
	}

	void newCircle(int no){
		if(circle_sz == 0){
			circle_sz = qtd_vert[no];
		}
		else{
			circle_sz = -1;
		}
	}

	int find(int no){
		if(pai[no] == no) return no;
		return pai[no] = find(pai[no]);
	}

	void merge(int a, int b){
		deg[a]++; deg[b]++;
		if(deg[a] > 2 || deg[b] > 2) circle_sz = -1;

		a = find(a); b = find(b);
		if(qtd_vert[a] < qtd_vert[b]) swap(a, b);// a será novo representante
		pai[b] = a;
		if(a != b) qtd_vert[a] += qtd_vert[b];
		else newCircle(a);
	}
};

int n, ROOT, V1, V2, V3;
UF princ, rt, v1, v2, v3;
vector<pair<int, int>> linked;
void Init(int N_) {
	n = N_;
	princ.N = n;
	princ.sub = false;
}

bool deg3 = false;
vector<int> adj[lim];

void buildSubUF(int root){
	deg3 = true;
	ROOT = root;
	V1 = adj[root][0];
	V2 = adj[root][1];
	V3 = adj[root][2];

	rt.N = n; rt.sub = true;
	v1.N = n; v1.sub = true;
	v2.N = n; v2.sub = true;
	v3.N = n; v3.sub = true;


	for(auto no : linked){
		int A = no.first, B = no.second;

		if(A != ROOT && B != ROOT) rt.merge(A, B);
		if(A != V1 && B != V1) v1.merge(A, B);
		if(A != V2 && B != V2) v2.merge(A, B);
		if(A != V3 && B != V3) v3.merge(A, B);
	}
}

void Link(int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
	linked.emplace_back(A, B);
	if(!deg3){ //link normal nos main UF
		princ.merge(A, B);

		if(princ.deg[A] > 2){
			buildSubUF(A);
			return;
		}
		if(princ.deg[B] > 2){
			buildSubUF(B);
			return;
		}
	}
	else{
		//link nos 4 sub UF;
		if(A != ROOT && B != ROOT) rt.merge(A, B);
		if(A != V1 && B != V1) v1.merge(A, B);
		if(A != V2 && B != V2) v2.merge(A, B);
		if(A != V3 && B != V3) v3.merge(A, B);
	}
}

int CountCritical() {
	// return n;
	if(deg3) return rt.CRings()+v1.CRings()+v2.CRings()+v3.CRings();
	else return princ.CRings();
}

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