oj.uz

Submission #151092

# Submission time Handle Problem Language Result Execution time Memory
151092 2019-09-01T17:24:57 Z pichulia Bulb Game (FXCUP4_bulb) C++17
0 / 100
 1000 ms 424 KB 
#include "bulb.h"
#include<algorithm>
using namespace std;
int n;
int parent[600009];
int value[600009];
int m;
int root;
int res;
vector<int> a;
vector<int> b;
vector<int> w;
void dfs(int si, int sum)
{
	if (si >= n) {
		if (value[si] == -1)
		{
			value[si] = sum;
		}
		return;
	}
	dfs(a[si], sum);
	dfs(b[si], sum + 1);
	value[si] = min(value[a[si]], value[b[si]]);
}
void dfs2(int si)
{
	if (si >= n) {
		return;
	}
	dfs2(a[si]);
	dfs2(b[si]);
	value[si] = min(value[a[si]], value[b[si]]);
}
void add_naive(int si, int val) {
	if (si >= n) {
		value[si] += val;
		return;
	}
	add_naive(a[si], val);
	add_naive(b[si], val);
	value[si] = min(value[a[si]], value[b[si]]);
}
void flip_naive(int si, int type) {
	if (type == 0) {
		add_naive(a[si], 1);
		add_naive(b[si], -1);
	}
	else {
		add_naive(a[si], -1);
		add_naive(b[si], 1);
	}
}
void dfs_type2(int si)
{
	if (si >= n)return;
	if (value[b[si]] > 2) { res = 1; return; }
	dfs_type2(b[si]);
	if (res == 1)return;
	dfs_type2(a[si]);
}
void precal(int si) {
	if (si >= n)return;
	if (value[a[si]] == 1) {
		w.push_back(si);
	}
	if(value[b[si]] == 1)
		precal(b[si]);
}
void deepdark(int si, int wi)
{
	if (si >= n)return;
	if (si != wi)
	{
		if (b[si] < n) {
			res = 0;
			return;
		}
		deepdark(a[si], wi);
	}
	else {
		if (a[si] < 0)
		{
			res = 0;
			return;
		}
		deepdark(b[si], wi);
	}
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	n = L.size();
	a = L;
	b = R;
	m = n;
	int i, j, k;
	for (i = 0; i < n; i++) {
		parent[i] = i;
	}
	for (i = 0; i < n; i++) {
		if (L[i] >= 0)
		{
			parent[L[i]] = i;
		}
		else {
			if (L[i] == -1)
				value[m] = 999999;
			else
				value[m] = -1;
			a[i] = m;
			parent[m] = i;
			m++;
		}
		if (R[i] >= 0)
		{
			parent[R[i]] = i;
		}
		else {
			if (R[i] == -1)
				value[m] = 999999;
			else
				value[m] = -1;
			b[i] = m;
			parent[m] = i;
			m++;
		}
	}
	for (i = 0; i < n; i++) { if (parent[i] == i)break; }
	root = i;
	res = 0;
	dfs(root, 0);
	if (value[root] == 0) return 0;
	if (n <= 1000) {
		for (i = 0; i < n; i++) {
			flip_naive(i, 0);
			for (j = 0; j < n; j++) {
				if (i == j) { flip_naive(j, 1); }
				else { flip_naive(j, 0); }
				dfs2(root);
				bool nono = false;
				if (value[root] == 0) nono = true;

				if (i == j) { flip_naive(j, 0); }
				else { flip_naive(j, 1); }

				if (nono)break;
			}
			flip_naive(i, 1);
			if (j == n) {
				//printf("%d is answer\n", i);
				break;
			}
		}
		return (i < n);
	}
	if (value[root] > 2)return 1;
	else if (value[root] == 2) {
		dfs_type2(root);
	}
	else {
		precal(root);
		if (w.size() > 1)return 0;
		if (w.size() == 0)
		{
			return 0;
		}
		else
		{
			flip_naive(w[0], 0);
			dfs2(root);
	//		printf("%d --> %d\n", w[0], value[root]);
			if (value[root] == 1) res = 0;
			else if (value[root] >= 2) res = 1;
			else {
				res = 1;
				deepdark(root, w[0]);
			}
		}
	}
	return res;
}

Compilation message

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:95:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 41 ms 380 KB Output is correct
4 Correct 34 ms 424 KB Output is correct
5 Correct 35 ms 376 KB Output is correct
6 Correct 41 ms 376 KB Output is correct
7 Correct 15 ms 376 KB Output is correct
8 Correct 93 ms 408 KB Output is correct
9 Correct 40 ms 400 KB Output is correct
10 Execution timed out 1053 ms 376 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 41 ms 380 KB Output is correct
6 Correct 34 ms 424 KB Output is correct
7 Correct 35 ms 376 KB Output is correct
8 Correct 41 ms 376 KB Output is correct
9 Correct 15 ms 376 KB Output is correct
10 Correct 93 ms 408 KB Output is correct
11 Correct 40 ms 400 KB Output is correct
12 Execution timed out 1053 ms 376 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 12 ms 376 KB Output is correct
5 Correct 41 ms 380 KB Output is correct
6 Correct 34 ms 424 KB Output is correct
7 Correct 35 ms 376 KB Output is correct
8 Correct 41 ms 376 KB Output is correct
9 Correct 15 ms 376 KB Output is correct
10 Correct 93 ms 408 KB Output is correct
11 Correct 40 ms 400 KB Output is correct
12 Execution timed out 1053 ms 376 KB Time limit exceeded
13 Halted 0 ms 0 KB -