Submission #1150756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150756		ChuanChen	낙하산 고리들 (IOI12_rings)	C++20	0 / 100	612 ms	125576 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;

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

	int CRings(){
		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);
	}
};

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

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 = UF(n);
	v1 = UF(n);
	v2 = UF(n);
	v3 = UF(n);

	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) {
	A++; 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() {
	if(deg3) return rt.CRings()+v1.CRings()+v2.CRings()+v3.CRings();
	else return princ.CRings();
}

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