oj.uz

Submission #151095

# Submission time Handle Problem Language Result Execution time Memory
151095 2019-09-01T17:29:18 Z pichulia Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 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);
		return;
	}
	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 <= 100) {
		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() == 0)
		{
			w.push_back(root);
		}
		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:96: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 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -