Submission #167519

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167519	2019-12-08T18:41:26 Z	faremy	Parachute rings (IOI12_rings)	C++14	55 / 100	4000 ms	87740 KB

rings

#include <algorithm>
#include <vector>


const int MAXN = 1e6;
int rings;

std::vector<int> graph[MAXN];
int parent[MAXN];
int ccSize[MAXN];

int candidate = -1;
int part = 0;
int last = -1;
bool isParticular[MAXN];

std::vector<int> listThree;
std::vector<int> listMore;
bool seen[MAXN];
bool adj[MAXN];


void Init(int N_)
{
	rings = N_;
	for (int iRing = 0; iRing < rings; iRing++)
	{
		parent[iRing] = iRing;
		ccSize[iRing] = 1;
	}
}

int find(int node)
{
	if (node != parent[node])
		parent[node] = find(parent[node]);
	return parent[node];
}

void fillLists(int node)
{
	if (seen[node])
		return;
	seen[node] = true;

	if (graph[node].size() == 3)
		listThree.emplace_back(node);
	else if (graph[node].size() > 3)
		listMore.emplace_back(node);
	for (int next : graph[node])
		fillLists(next);
}

int nogood(int node, int root)
{
	if (seen[node])
		return 0;
	seen[node] = true;

	int degOffset = 0;
	for (int next : graph[node])
		if (next == root)
			degOffset++;

	if (graph[node].size() - degOffset == 3)
		return -1;

	int ans = (graph[node].size() - degOffset <= 1);
	for (int next : graph[node])
	{
		int sub = nogood(next, root);
		if (sub == -1)
			return -1;
		ans |= sub;
	}

	return ans;
}

bool iscrit(int node)
{
	if (adj[node])
		return false;
	adj[node] = true;
	std::fill_n(seen, rings, false);
	seen[node] = true;

	for (int start : graph[node])
		if (!seen[start] && nogood(start, node) < 1)
			return false;
	return true;
}

int check(int node)
{
	listThree.clear();
	listMore.clear();
	std::fill_n(seen, rings, false);
	std::fill_n(adj, rings, false);

	fillLists(node);
	if (listThree.empty() && listMore.empty())
		return ccSize[node];

	if (listMore.size() > 1)
	{
		candidate = -2;
		return 0;
	}

	if (listMore.size() == 1)
	{
		if (iscrit(listMore[0]))
			return 1;
		candidate = -2;
		return 0;
	}

	if (listThree.size() > 4)
	{
		candidate = -2;
		return 0;
	}

	if (listThree.size() < 3)
	{
		int ans = 0;
		for (int root : listThree)
		{
			ans += iscrit(root);
			for (int nxt : graph[root])
				ans += iscrit(nxt);
		}

		if (ans == 0)
			candidate = -2;
		return ans;
	}

	int ans = 0;
	for (int root : listThree)
		ans += iscrit(root);

	if (ans == 0)
		candidate = -2;
	return ans;
}

void Link(int A, int B)
{
	if (candidate == -2)
		return;
	int ccA = find(A);
	int ccB = find(B);

	graph[A].emplace_back(B);
	graph[B].emplace_back(A);

	if (ccA == ccB)
	{
		part += !isParticular[ccA];
		isParticular[ccA] = true;
		last = -1;
	}
	else
	{
		if (ccSize[ccA] < ccSize[ccB])
			std::swap(ccA, ccB);
		parent[ccB] = ccA;
		ccSize[ccA] += ccSize[ccB];

		if (isParticular[ccA] && isParticular[ccB])
		{
			part--;
			last = -1;
		}

		isParticular[ccA] |= isParticular[ccB];
		if (graph[A].size() == 3 || graph[A].size() == 4 || graph[B].size() == 3 || graph[B].size() == 4)
		{
			part += !isParticular[ccA];
			isParticular[ccA] = true;
			last = -1;
		}
		else if (graph[A].size() > 4 || graph[B].size() > 4)
		{
			isParticular[ccA] = true;
		}
	}

	if (isParticular[ccA] && candidate != -2)
		candidate = ccA;
}

int CountCritical()
{
	if (candidate == -2)
		return 0;
	if (part == 0)
		return rings;
	if (part > 1)
		return 0;
	if (last == -1)
		last = check(candidate);
	return last;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23800 KB	Output is correct
2	Correct	26 ms	24184 KB	Output is correct
3	Correct	28 ms	24056 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	26 ms	24040 KB	Output is correct
6	Correct	26 ms	24312 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	27 ms	24056 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	427 ms	44760 KB	Output is correct
2	Correct	918 ms	57708 KB	Output is correct
3	Correct	1061 ms	59920 KB	Output is correct
4	Correct	1177 ms	65784 KB	Output is correct
5	Correct	1153 ms	66916 KB	Output is correct
6	Correct	1267 ms	87740 KB	Output is correct
7	Correct	991 ms	59384 KB	Output is correct
8	Correct	1068 ms	63416 KB	Output is correct
9	Correct	1139 ms	66620 KB	Output is correct
10	Correct	818 ms	61436 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23800 KB	Output is correct
2	Correct	26 ms	24184 KB	Output is correct
3	Correct	28 ms	24056 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	26 ms	24040 KB	Output is correct
6	Correct	26 ms	24312 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	27 ms	24056 KB	Output is correct
11	Correct	25 ms	24056 KB	Output is correct
12	Correct	29 ms	24568 KB	Output is correct
13	Correct	30 ms	24528 KB	Output is correct
14	Correct	41 ms	24184 KB	Output is correct
15	Correct	46 ms	24184 KB	Output is correct
16	Correct	28 ms	24312 KB	Output is correct
17	Correct	28 ms	24312 KB	Output is correct
18	Correct	30 ms	24440 KB	Output is correct
19	Correct	29 ms	24312 KB	Output is correct
20	Correct	28 ms	24312 KB	Output is correct

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23800 KB	Output is correct
2	Correct	26 ms	24184 KB	Output is correct
3	Correct	28 ms	24056 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	26 ms	24040 KB	Output is correct
6	Correct	26 ms	24312 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	27 ms	24056 KB	Output is correct
11	Correct	25 ms	24056 KB	Output is correct
12	Correct	29 ms	24568 KB	Output is correct
13	Correct	30 ms	24528 KB	Output is correct
14	Correct	41 ms	24184 KB	Output is correct
15	Correct	46 ms	24184 KB	Output is correct
16	Correct	28 ms	24312 KB	Output is correct
17	Correct	28 ms	24312 KB	Output is correct
18	Correct	30 ms	24440 KB	Output is correct
19	Correct	29 ms	24312 KB	Output is correct
20	Correct	28 ms	24312 KB	Output is correct
21	Correct	43 ms	25336 KB	Output is correct
22	Correct	56 ms	26204 KB	Output is correct
23	Correct	67 ms	26844 KB	Output is correct
24	Execution timed out	4035 ms	26476 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23800 KB	Output is correct
2	Correct	26 ms	24184 KB	Output is correct
3	Correct	28 ms	24056 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	26 ms	24040 KB	Output is correct
6	Correct	26 ms	24312 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	27 ms	24056 KB	Output is correct
11	Correct	427 ms	44760 KB	Output is correct
12	Correct	918 ms	57708 KB	Output is correct
13	Correct	1061 ms	59920 KB	Output is correct
14	Correct	1177 ms	65784 KB	Output is correct
15	Correct	1153 ms	66916 KB	Output is correct
16	Correct	1267 ms	87740 KB	Output is correct
17	Correct	991 ms	59384 KB	Output is correct
18	Correct	1068 ms	63416 KB	Output is correct
19	Correct	1139 ms	66620 KB	Output is correct
20	Correct	818 ms	61436 KB	Output is correct
21	Correct	25 ms	24056 KB	Output is correct
22	Correct	29 ms	24568 KB	Output is correct
23	Correct	30 ms	24528 KB	Output is correct
24	Correct	41 ms	24184 KB	Output is correct
25	Correct	46 ms	24184 KB	Output is correct
26	Correct	28 ms	24312 KB	Output is correct
27	Correct	28 ms	24312 KB	Output is correct
28	Correct	30 ms	24440 KB	Output is correct
29	Correct	29 ms	24312 KB	Output is correct
30	Correct	28 ms	24312 KB	Output is correct
31	Correct	43 ms	25336 KB	Output is correct
32	Correct	56 ms	26204 KB	Output is correct
33	Correct	67 ms	26844 KB	Output is correct
34	Execution timed out	4035 ms	26476 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-