Submission #167518

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167518	2019-12-08T18:40:37 Z	faremy	Parachute rings (IOI12_rings)	C++14	55 / 100	4000 ms	89656 KB

rings

#include <algorithm>
#include <vector>
#include <iostream>


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	23 ms	23800 KB	Output is correct
2	Correct	25 ms	24060 KB	Output is correct
3	Correct	25 ms	24184 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24056 KB	Output is correct
6	Correct	26 ms	24284 KB	Output is correct
7	Correct	25 ms	23928 KB	Output is correct
8	Correct	25 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	26 ms	24184 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	418 ms	47864 KB	Output is correct
2	Correct	878 ms	59832 KB	Output is correct
3	Correct	1069 ms	61904 KB	Output is correct
4	Correct	1195 ms	67832 KB	Output is correct
5	Correct	1148 ms	68856 KB	Output is correct
6	Correct	1291 ms	89656 KB	Output is correct
7	Correct	1040 ms	61504 KB	Output is correct
8	Correct	1158 ms	65432 KB	Output is correct
9	Correct	1189 ms	68572 KB	Output is correct
10	Correct	772 ms	74232 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	25 ms	24060 KB	Output is correct
3	Correct	25 ms	24184 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24056 KB	Output is correct
6	Correct	26 ms	24284 KB	Output is correct
7	Correct	25 ms	23928 KB	Output is correct
8	Correct	25 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	26 ms	24184 KB	Output is correct
11	Correct	26 ms	24184 KB	Output is correct
12	Correct	29 ms	24696 KB	Output is correct
13	Correct	29 ms	24568 KB	Output is correct
14	Correct	42 ms	24312 KB	Output is correct
15	Correct	47 ms	24316 KB	Output is correct
16	Correct	29 ms	24440 KB	Output is correct
17	Correct	28 ms	24428 KB	Output is correct
18	Correct	30 ms	24568 KB	Output is correct
19	Correct	30 ms	24440 KB	Output is correct
20	Correct	31 ms	24468 KB	Output is correct

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	25 ms	24060 KB	Output is correct
3	Correct	25 ms	24184 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24056 KB	Output is correct
6	Correct	26 ms	24284 KB	Output is correct
7	Correct	25 ms	23928 KB	Output is correct
8	Correct	25 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	26 ms	24184 KB	Output is correct
11	Correct	26 ms	24184 KB	Output is correct
12	Correct	29 ms	24696 KB	Output is correct
13	Correct	29 ms	24568 KB	Output is correct
14	Correct	42 ms	24312 KB	Output is correct
15	Correct	47 ms	24316 KB	Output is correct
16	Correct	29 ms	24440 KB	Output is correct
17	Correct	28 ms	24428 KB	Output is correct
18	Correct	30 ms	24568 KB	Output is correct
19	Correct	30 ms	24440 KB	Output is correct
20	Correct	31 ms	24468 KB	Output is correct
21	Correct	44 ms	25936 KB	Output is correct
22	Correct	58 ms	26768 KB	Output is correct
23	Correct	67 ms	27640 KB	Output is correct
24	Execution timed out	4033 ms	26208 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	25 ms	24060 KB	Output is correct
3	Correct	25 ms	24184 KB	Output is correct
4	Correct	23 ms	23928 KB	Output is correct
5	Correct	24 ms	24056 KB	Output is correct
6	Correct	26 ms	24284 KB	Output is correct
7	Correct	25 ms	23928 KB	Output is correct
8	Correct	25 ms	24056 KB	Output is correct
9	Correct	26 ms	24184 KB	Output is correct
10	Correct	26 ms	24184 KB	Output is correct
11	Correct	418 ms	47864 KB	Output is correct
12	Correct	878 ms	59832 KB	Output is correct
13	Correct	1069 ms	61904 KB	Output is correct
14	Correct	1195 ms	67832 KB	Output is correct
15	Correct	1148 ms	68856 KB	Output is correct
16	Correct	1291 ms	89656 KB	Output is correct
17	Correct	1040 ms	61504 KB	Output is correct
18	Correct	1158 ms	65432 KB	Output is correct
19	Correct	1189 ms	68572 KB	Output is correct
20	Correct	772 ms	74232 KB	Output is correct
21	Correct	26 ms	24184 KB	Output is correct
22	Correct	29 ms	24696 KB	Output is correct
23	Correct	29 ms	24568 KB	Output is correct
24	Correct	42 ms	24312 KB	Output is correct
25	Correct	47 ms	24316 KB	Output is correct
26	Correct	29 ms	24440 KB	Output is correct
27	Correct	28 ms	24428 KB	Output is correct
28	Correct	30 ms	24568 KB	Output is correct
29	Correct	30 ms	24440 KB	Output is correct
30	Correct	31 ms	24468 KB	Output is correct
31	Correct	44 ms	25936 KB	Output is correct
32	Correct	58 ms	26768 KB	Output is correct
33	Correct	67 ms	27640 KB	Output is correct
34	Execution timed out	4033 ms	26208 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-