Submission #364440

#	Time	Username	Problem	Language	Result	Execution time	Memory
364440		shivensinha4	Parachute rings (IOI12_rings)	C++17	0 / 100	1660 ms	114652 KiB

rings

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#ifndef mlocal
//#include "grader.h"
//#endif
#define endl '\n'

// TODO: check if at max one component is bad
vector<vi> adj, ct;
vi oc, tc, sz;
vector<bool> isCrit, isBadComp;
int crit = 0, n, over = 0, bct = 0, badComp = 0;
bool badFound = false, dunCheck = false;

class UFDS {
public:
	vi p, rank; int count = 0;
	
	void build() {
		p.resize(n); rank.resize(n);
		for_(i, 0, n) p[i] = i;
		count = n;
	}
	int getParent(int i) {
		return (p[i] == i) ? i : (p[i] = getParent(p[i]));
	}
	
	void setBad(int i) {
//		cout << "oof bad " << oc[i] << " " << tc[i] << " " << sz[i] << endl;
		isBadComp[i] = true; badComp++;
		if (badComp > 1) {
			crit = 0;
			dunCheck = true;
		}
	}
	
	void check(int i) {
		i = getParent(i);
		if (isBadComp[i]) return;
		if (oc[i] != 2 or oc[i]+tc[i] != sz[i]) setBad(i);
	}
	
	void join(int i, int j) {
		int a = getParent(i), b = getParent(j);
		
		if (a != b) {
			count -= 1;
			oc[a] = oc[b] = oc[a]+oc[b];
			tc[a] = tc[b] = tc[a]+tc[b];
			sz[a] = sz[b] = sz[a]+sz[b];
			isBadComp[a] = isBadComp[b] = isBadComp[a] or isBadComp[b];
			
			if (rank[a] > rank[b]) {
				p[b] = a;
			} else {
				p[a] = b;
				if (rank[a] == rank[b]) rank[b] += 1;
			}
		}
		
		check(a);
	}
};

UFDS ufds;

void updateAdj(int p) {
	int k = adj[p].size(), pp = ufds.getParent(p);
	
	if (k == 4) over++;
	else if (k == 3) {
		bct++;
		tc[pp]--;
	}
	else if (k == 2) {
		oc[pp]--;
		tc[pp]++;
//		cout << "removing oc " << p << endl;
	}
	else if (k == 1) {
		oc[pp]++;
//		cout << "adding oc " << p << endl;
	}
	
	if (k > 3) return;
	for_(i, 0, adj[p].size()) {
		if (i != (int) adj[p].size()-1) ct[adj[p][i]][k-1] -= 1;
		ct[adj[p][i]][k] += 1;
	}
}

void find(int p) {
	int k = adj[p].size();
	if (k > 3) return;
	if (badComp and !isBadComp[ufds.getParent(p)]) return;
	
	for (auto i: adj[p]) {
		bool temp = ct[i][3] == bct and ct[i][2] >= (2-oc[ufds.getParent(i)]);
		
		if (temp and !isCrit[i]) crit++;
		else if (!temp and isCrit[i]) crit--;
		
		isCrit[i] = temp;
	}
}


void Init(int N) {
	n = N;
	ufds.build(); adj.resize(n); ct.resize(n, vi(4)); isCrit.resize(n); oc.resize(n); isBadComp.resize(n); sz.resize(n, 1); tc.resize(n);
}

void Link(int a, int b) {
	if (dunCheck) return;
	
	adj[a].push_back(b); adj[b].push_back(a);
	updateAdj(a); updateAdj(b);
	ufds.join(a, b);
	
	if (over > 1) {
		crit = 0;
		dunCheck = true;
	}
	
	if (dunCheck) return;
	
	find(a); find(b);
}

int CountCritical() {
	if (badComp == 0) return n;
	else return crit;
}


//int main() {
//#ifdef mlocal
//	freopen("test.in", "r", stdin);
//#endif
//
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);
//
////	Init(7);
////	cout << CountCritical() << endl;
////	Link(1, 2);
////	cout << CountCritical() << endl;
////	Link(0, 5);
////	cout << CountCritical() << endl;
////	Link(2, 0);
////	cout << CountCritical() << endl;
////	Link(3, 2);
////	cout << CountCritical() << endl;
////	Link(3, 5);
////	cout << CountCritical() << endl;
////	Link(4, 3);
////	cout << CountCritical() << endl;
//
//	Init(7);
//	cout << CountCritical() << endl;
//	Link(0, 1);
//	cout << CountCritical() << endl;
//	Link(1, 2);
//	cout << CountCritical() << endl;
//	Link(0, 2);
//	cout << CountCritical() << endl;
//	Link(3, 4);
//	cout << CountCritical() << endl;
//	Link(4, 5);
//	cout << CountCritical() << endl;
//	Link(3, 5);
//	cout << CountCritical() << endl;
//
//	return 0;
//}

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