Submission #26595

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26595	2017-07-03T12:19:10 Z	model_code	Conspiracy (POI11_kon)	C++11	50 / 100	3000 ms	123616 KB

/*************************************************************************}
{*                                                                       *}
{*   Zadanie: Konspiracja (KON)                                          *}
{*   Plik:    kons5.cpp                                                  *}
{*   Autor:   Bartosz Górski                                             *}
{*   Opis:    Rozwiązanie nieefektywne czasowo                           *}
{*            Złożoność: O(n ^ 4)                                        *}
{*            Kodowanie znaków: UTF-8                                    *}
{*                                                                       *}
{*************************************************************************/

#include<cstdio>
#include<algorithm>
#include<assert.h>
using namespace std;

#define MAX_N 5000

int n, m, k, a, order[2 * MAX_N], io;
bool graph[2 * MAX_N][2 * MAX_N], visit[2 * MAX_N];
char edgeColour[MAX_N][MAX_N], vertexColour[MAX_N], colour[2 * MAX_N];

void init(int n) {
	m = 2 * n;
	for(int i = 0; i < n; ++i) {
		vertexColour[i] = '?';
		for(int j = 0; j < n; ++j)
			edgeColour[i][j] = 'B';
	}
}

void readGraph() {
	assert(scanf("%d", &n) == 1);
	init(n);
	for(int i = 0; i < n; ++i) {
		assert(scanf("%d", &k) == 1);
		for(int j = 0; j < k; ++j) {
			assert(scanf("%d", &a) == 1);
			edgeColour[i][a - 1] = 'R';
		}
	}
}

bool check() {
	bool res = true;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			if(edgeColour[i][j] != vertexColour[i] && edgeColour[i][j] != vertexColour[j])
				res = false;
	return res;
}

void reverseDfs(int a) {
	visit[a] = true;
	for(int i = 0; i < m; ++i)
		if(graph[i][a] && !visit[i])
			reverseDfs(i);
	order[io++] = a;
}

void paintDfs(int a) {
	visit[a] = true;
	if(colour[a ^ 1] == '?')
		colour[a] = 'R';
	else
		colour[a] = 'B';
	for(int i = 0; i < m; ++i)
		if(graph[a][i] && !visit[i])
			paintDfs(i);
}

bool findSolution() {
	for(int i = 0; i < m; ++i)
		for(int j = 0; j < m; ++j)
			graph[i][j] = false;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j < n; ++j)
			if(edgeColour[i][j] == 'R')
				graph[2 * i + 1][2 * j] = graph[2 * j + 1][2 * i] = true;
			else
				graph[2 * i][2 * j + 1] = graph[2 * j][2 * i + 1] = true;				
	for(int i = 0; i < m; ++i) {
		visit[i] = false;
		colour[i] = '?';
	}
	for(int i = 0; i < m; ++i)
		if(!visit[i])
			reverseDfs(i);
	for(int i = 0; i < m; ++i)
		visit[i] = false;
	for(int i = m - 1; i >= 0; --i)
		if(!visit[order[i]])
			paintDfs(order[i]);
	for(int i = 0; i < m; ++i)
		for(int j = 0; j < m; ++j)
			if(graph[i][j] && colour[i] == 'R' && colour[j] == 'B')
				return false;
	for(int i = 0; i < n; ++i)
		vertexColour[i] = colour[2 * i];
	return true;
}

char oppositeColour(char colour) {
	if(colour == 'R')
		return 'B';
	return 'R';
}

int solve() {
	if(!findSolution())
		return 0;
	int  red[MAX_N], blue[MAX_N], ir = 0, ib = 0;
	for(int i = 0; i < n; ++i)
		if(vertexColour[i] == 'R')
			red[ir++] = i;
		else
			blue[ib++] = i;
	int res = 1;
	for(int i = 0; i < ir; ++i)
		for(int j = 0; j < ib; ++j) {
			swap(vertexColour[red[i]], vertexColour[blue[j]]);
			if(check())
				++res;
			swap(vertexColour[red[i]], vertexColour[blue[j]]);
		}
	for(int i = 0; i < n; ++i) {
		vertexColour[i] = oppositeColour(vertexColour[i]);
		if(check())
			++res;
		vertexColour[i] = oppositeColour(vertexColour[i]);
	}
	if(res > n)
		--res;
	return res;
}

int main() {
	readGraph();	
	printf("%d\n", solve());
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	123252 KB	Output is correct
2	Correct	123252 KB	Output is correct
3	Correct	123252 KB	Output is correct
4	Correct	123252 KB	Output is correct
5	Correct	123252 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	123252 KB	Output is correct
2	Correct	123252 KB	Output is correct
3	Correct	123252 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	123252 KB	Output is correct
2	Correct	9 ms	123252 KB	Output is correct
3	Correct	6 ms	123252 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	123252 KB	Output is correct
2	Correct	813 ms	123252 KB	Output is correct
3	Correct	36 ms	123252 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	123252 KB	Output is correct
2	Correct	2166 ms	123252 KB	Output is correct
3	Correct	163 ms	123252 KB	Output is correct

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	123292 KB	Output is correct
2	Execution timed out	3000 ms	123252 KB	Execution timed out
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	123308 KB	Output is correct
2	Execution timed out	3000 ms	123252 KB	Execution timed out
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	589 ms	123404 KB	Output is correct
2	Execution timed out	3000 ms	123272 KB	Execution timed out
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1629 ms	123528 KB	Output is correct
2	Execution timed out	3000 ms	123328 KB	Execution timed out
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3000 ms	123616 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Submission #26595

Compilation message