제출 #74163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74163		Bruteforceman	낙하산 고리들 (IOI12_rings)	C++11	100 / 100	3944 ms	146500 KiB

rings

#include "bits/stdc++.h"
using namespace std;
int N;
struct dsu {
	bool cycle[1000010];
	int head[1000010];
	int tail[1000010];
	int par[1000010];
	int len[1000010];
	int cycle_cnt;
	int cycle_sum;
	bool bad;
	int no_of_nodes;
	int del_node;

	void init (int n) {
		no_of_nodes = n;
		del_node = -1;
		for(int i = 0; i < no_of_nodes; i++) {
			cycle[i] = false;
			head[i] = tail[i] = par[i] = i;
			len[i] = 1;
		}
		cycle_cnt = 0;
		cycle_sum = 0;
		bad = false;
	}
	int root(int x) {
		if(x == par[x]) return par[x];
		return par[x] = root(par[x]);
	}
	void add(int x, int y) {
		if(del_node == x || del_node == y) return ; 
		if(bad) return ;
		int p = root(x);
		int q = root(y);
		if(p == q) {
			if(cycle[p]) {
				bad = true;
				return ;
			} else if(head[p] == x && tail[p] == y) {
				cycle_cnt += 1;
				cycle_sum += len[p];
				cycle[p] = true;
			} else if (head[p] == y && tail[p] == x) {
				cycle_cnt += 1;
				cycle_sum += len[p];
				cycle[p] = true;
			} else {
				bad = true;
				return ;
			}
		} else {
			if(cycle[p] || cycle[q]) {
				bad = true;
				return ;
			}
			par[p] = q;
			len[q] += len[p];
			if(x == head[p]) {
				if(y == head[q]) {
					head[q] = tail[p];
				} else if (y == tail[q]) {
					tail[q] = tail[p];
				} else {
					bad = true;
					return ;
				}
			} else if (x == tail[p]) {
				if(y == head[q]) {
					head[q] = head[p];
				} else if (y == tail[q]) {
					tail[q] = head[p];
				} else {
					bad = true;
					return ;
				}
			} else {
				bad = true;
				return ;
			}
		}
	}
	int count() {
		if(bad) return 0;
		if(cycle_cnt <= 1) {
			if(cycle_cnt == 1) return cycle_sum;
			else return no_of_nodes;
		}
		return 0;
	}
} T[5];
vector <int> g[1000010];
vector <int> l, r;
bool found_cand;

void Init(int N_) {
  N = N_;
  for(int i = 0; i < 5; i++) {
  	T[i].init(N);
  }
  for(int i = 0; i < N; i++) {
  	g[i].clear();
  }
  l.clear(); r.clear();
  found_cand = false;
}



void Link(int A, int B) {
	if(found_cand) {
		for(int i = 1; i <= 4; i++) {
			T[i].add(A, B);
		}
		return ;
	}
	l.emplace_back(A);
	r.emplace_back(B);
	g[A].emplace_back(B);
	g[B].emplace_back(A);
	if(g[A].size() == 3) {
		T[1].del_node = A;
		T[2].del_node = g[A][0];
		T[3].del_node = g[A][1];
		T[4].del_node = g[A][2];
		found_cand = true;
	} else if (g[B].size() == 3) {
		T[1].del_node = B;
		T[2].del_node = g[B][0];
		T[3].del_node = g[B][1];
		T[4].del_node = g[B][2];	
		found_cand = true;
	} else {
		T[0].add(A, B);
	}
	if(found_cand) {
		for(int i = 0; i < (int)l.size(); i++) {
			Link(l[i], r[i]);
		}
	}
}

int CountCritical() {
	if(found_cand) {
		int ans = 0;
		for(int i = 1; i <= 4; i++) {
			if(T[i].cycle_cnt == 0 && !T[i].bad) {
				++ans;
			}
 		}
 		return ans;
	}
	return T[0].count();
}

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