oj.uz

Submission #1090138

# Submission time Handle Problem Language Result Execution time Memory
1090138 2024-09-17T19:24:39 Z Gourougourou Conspiracy (POI11_kon) C++17
50 / 100
 3000 ms 72228 KB 
/*************************************************************************}
{*                                                                       *}
{*   Zadanie: Konspiracja (KON)                                          *}
{*   Plik:    kons3.cpp                                                  *}
{*   Autor:   Bartosz Górski                                             *}
{*   Opis:    Rozwiązanie nieefektywne czasowo                           *}
{*            Złożoność: O(n ^ 3)                                        *}
{*            Kodowanie znaków: UTF-8                                    *}
{*                                                                       *}
{*************************************************************************/

#include<cstdio>
#include<assert.h>

#define MAX_N 5000

int n, k, a;
char edgeColour[MAX_N][MAX_N], vertexColour[MAX_N];

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

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';
		}
	}
}

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

bool go(int v, char colour) {
	if(vertexColour[v] != '?')
		return vertexColour[v] == colour;
	vertexColour[v] = colour;
	bool res = true;
	for(int i = 0; i < n && res; ++i)
		if(i != v && (vertexColour[v] == '?' || 
				edgeColour[v][i] == oppositeColour(vertexColour[v])))
			res &= go(i, edgeColour[v][i]);
	return res;
}

bool check(int a, int b, int c) {
	if(edgeColour[a][b] == edgeColour[a][c] && edgeColour[a][b] != edgeColour[b][c])
		return go(a, edgeColour[a][b]);
	return true;
}

int solve() {
	for(int a = 0; a < n; ++a)
		for(int b = a + 1; b < n; ++b)
			for(int c = b + 1; c < n; ++c)
				if(!check(a, b, c) || !check(b, a, c) || !check(c, a, b))
					return 0;
	int res = 1;
	for(int i = 0; i < n; ++i)
		if(vertexColour[i] == '?')
			++res;
	if(res > n)
		--res;
	return res;
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 9 ms 1116 KB Output is correct
3 Correct 3 ms 1048 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 17 ms 3580 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7004 KB Output is correct
2 Correct 1741 ms 10620 KB Output is correct
3 Execution timed out 3059 ms 22356 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8024 KB Output is correct
2 Execution timed out 3079 ms 13804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15192 KB Output is correct
2 Execution timed out 3064 ms 22368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 24220 KB Output is correct
2 Execution timed out 3045 ms 40368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 72228 KB Output is correct
2 Execution timed out 3079 ms 55664 KB Time limit exceeded
3 Halted 0 ms 0 KB -