Submission #74239

#	Time	Username	Problem	Language	Result	Execution time	Memory
74239		admin	Parachute rings (IOI12_rings)	C++17	100 / 100	2079 ms	42560 KiB

rings

#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"
using namespace std;
int N;
struct dsu {
	int other[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++) {
			other[i] = i;
			len[i] = 1;
		}
		cycle_cnt = 0;
		cycle_sum = 0;
		bad = false;
	}
	void add(int x, int y) {
		if(del_node == x || del_node == y) return ; 
		if(bad) return ;
		if(other[x] == y) {
			other[x] = -1;
			other[y] = -1;
			cycle_cnt += 1;
			cycle_sum += len[x];
		} else {
			if(other[x] == -1 || other[y] == -1) {
				bad = true;
				return ;
			}
			int p = other[y];
			int q = other[x];
			other[p] = q;
			other[q] = p;
			int sum = len[x] + len[y];
			len[p] = len[q] = sum;
			if(x != p && x != q) {
				other[x] = -1;
			}
			if(y != p && y != q) {
				other[y] = -1;
			}
		}
	}
	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[4];
int deg[1000010];
vector <int> l, r;
bool found_cand;
 
void Init(int N_) {
  N = N_;
  T[0].init(N);
  for(int i = 0; i < N; i++) {
  	deg[i] = 0;
  }
  l.clear(); r.clear();
  found_cand = false;
}
void Link(int A, int B) {
	if(found_cand) {
		for(int i = 0; i < 4; i++) {
			T[i].add(A, B);
		}
		return ;
	}
	++deg[A]; ++deg[B];
	l.emplace_back(A);
	r.emplace_back(B);
	if(deg[A] == 3 || deg[B] == 3) {
		vector <int> v;
		int can = deg[A] == 3 ? A : B;
		v.emplace_back(can);
		for(int i = 0; i < (int) l.size(); i++) {
			if(l[i] == can || r[i] == can) {
				v.emplace_back(l[i] ^ r[i] ^ can);
			}
		}
		for(int i = 0; i < 4; i++) {
			T[i].init(N);
			T[i].del_node = v[i];
		}
		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]);
		}
 		l.clear(); r.clear();
	}
}
 
int CountCritical() {
	if(found_cand) {
		int ans = 0;
		for(int i = 0; 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