Submission #63422

#	Time	Username	Problem	Language	Result	Execution time	Memory
63422		zadrga	Parachute rings (IOI12_rings)	C++14	100 / 100	2357 ms	133144 KiB

rings

// 19.44

#include <bits/stdc++.h>

using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 1000111
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

struct DSU{
	bool over;
	int n, owner, max_degree, type;
	set<int> cycles;
	int deg[maxn];
	int sz[maxn];
	int root[maxn];

	int rooting(int x){
		if(root[x] == x)
			return x;
		return root[x] = rooting(root[x]);
	}

	void addEdge(int a, int b){
		if(a == owner || b == owner || over == 1)
			return;

		int ra = rooting(a);
		int rb = rooting(b);
		deg[a]++; deg[a] = min(deg[a], 3);
		deg[b]++; deg[b] = min(deg[b], 3);

		max_degree = max(max_degree, max(deg[a], deg[b]));

		if(ra != rb){
			root[rb] = ra;
			sz[ra] += sz[rb];
		} 

		if(ra == rb)
			cycles.insert(ra);

		if(max_degree == 3 || cycles.size() > 1)
			over = 1;

		if(type >= 3 && cycles.size() == 1)
			over = 1;
	}

	void init(int nn, int x, int t, vector<pii> &edge){
		n = nn;
		owner = x;
		max_degree = over = 0;
		type = t;
		for(int i = 0; i < maxn; i++){
			root[i] = i;
			deg[i] = 0;
			sz[i] = 1;
		}

		for(pii v : edge)
			addEdge(v.fi, v.se);
	}

	int getAns(){
		if(over)
			return 0;

		if(type == 2){
			if(max_degree <= 1)
				return n;

			if(max_degree == 2){
				if(cycles.size() == 0)
					return n;

				if(cycles.size() == 1)
					return sz[*cycles.begin()];
			}
		}

		if(type == 3 || type == 4)
			return 1;	
	}
} dsu[6];
 

bool start[6];
int deg[maxn], num[5], ind[5], n;
vector<pii> edge;
vector<int> adj[maxn];
pii cur_range;
int all_max_degree;


void Init(int N){
	n = N;
	all_max_degree = 0;
	dsu[0].init(n, -1, 2, edge);
	memset(ind, -1, sizeof(ind));
	num[0] = n;
	start[0] = 1;
	cur_range = mp(0, 0);
}
 
void Link(int A, int B){
	adj[A].pb(B);
	adj[B].pb(A);

	num[deg[A]]--;
	deg[A]++; deg[A] = min(deg[A], 4);
	num[deg[A]]++;

	if(ind[deg[A]] == -1)
		ind[deg[A]] = A;

	num[deg[B]]--;
	deg[B]++; deg[B] = min(deg[B], 4);
	num[deg[B]]++;

	if(ind[deg[B]] == -1)
		ind[deg[B]] = B;

	all_max_degree = max(all_max_degree, max(deg[A], deg[B]));

	if(all_max_degree == 3){
		cur_range = mp(1, 4);
		if(!start[1]){
			start[1] = 1;
			int cnt = 1;
			dsu[cnt++].init(n, ind[3], 3, edge);
			for(int v : adj[ind[3]])
				dsu[cnt++].init(n, v, 3, edge);
		}
	}

	if(all_max_degree == 4){
		cur_range = mp(5, 5);
		if(!start[5]){
			start[5] = 1;
			dsu[5].init(n, ind[4], 4, edge);
		}
	}

	edge.pb(mp(A, B));
	for(int i = cur_range.fi; i <= cur_range.se; i++)
		dsu[i].addEdge(A, B);
}
 
int CountCritical(){ 
	int ret = 0;
	for(int i = cur_range.fi; i <= cur_range.se; i++)
		ret += dsu[i].getAns();
	return ret;
}

Compilation message (stderr)

rings.cpp: In member function 'int DSU::getAns()':
rings.cpp:93:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

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