Submission #576092

#	Time	Username	Problem	Language	Result	Execution time	Memory
576092		benson1029	Parachute rings (IOI12_rings)	C++14	100 / 100	1612 ms	213540 KiB

rings

#include<bits/stdc++.h>
using namespace std;
int N;

vector<int> edg[1000005];
int DEG3 = -1;
int DEG4 = -1;
bool choicesToggle = false;
set<int> choices, tmp;
int dsu[1000005];
int cyc[1000005];
bool vis[1000005];
int pre[1000005];
int cyccnt = 0;
int GG = 0;
vector<int> undolist;

int find(int x) {
	if(dsu[x]==x)return x;
	return dsu[x] = find(dsu[x]);
}

void setintersection(set<int> tmp) {
	if(!choicesToggle) {
		choicesToggle = true;
		choices = tmp;
		return;
	}
	set<int> tmp2;
	for(int i:tmp) {
		if(choices.find(i)!=choices.end()) {
			tmp2.insert(i);
		}
	}
	choices = tmp2;
}

void dfs(int x, int p, int tar) {
	vis[x] = true;
	pre[x] = p;
	undolist.push_back(x);
	if(x==tar) {
		int ptr = pre[tar];
		tmp.clear();
		tmp.insert(tar);
		while(ptr != tar) {
			tmp.insert(ptr);
			ptr = pre[ptr];
		}
		setintersection(tmp);
		return;
	}
	for(int i:edg[x]) {
		if(i==p) continue;
		if(!vis[i]) dfs(i, x, tar);
	}
}

void merge(int x, int y) {
	if(find(x)==find(y)) {
		cyc[find(x)]++;
		if(cyc[find(x)]<=3) dfs(x, y, y);
		for(int i:undolist) vis[i] = false;
		undolist.clear();
		if(cyc[find(x)]==2) {
			tmp.clear();
			for(int i:choices) {
				if(edg[i].size()>=3) tmp.insert(i);
			}
			choices = tmp;
		}
	} else {
		cyc[find(x)] += cyc[find(y)];
		dsu[find(y)] = find(x);
	}
}

void Init(int N_) {
	N = N_;
	for(int i=0; i<N; i++) dsu[i] = i;
}


void Link(int A, int B) {
	if(GG) return;
	edg[A].push_back(B);
	edg[B].push_back(A);
	merge(A, B);
	if(edg[A].size()==4) setintersection({A});
	else if(edg[A].size()==3) setintersection({A, edg[A][0], edg[A][1], edg[A][2]});
	if(edg[B].size()==4) setintersection({B});
	else if(edg[B].size()==3) setintersection({B, edg[B][0], edg[B][1], edg[B][2]});
}

int CountCritical() {
	if(GG) return 0;
	if(!choicesToggle) return N;
	else return choices.size();
}

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