Submission #150951

# Submission time Handle Problem Language Result Execution time Memory
150951 2019-09-01T12:54:47 Z dennisstar Bulb Game (FXCUP4_bulb) C++17
0 / 100
2 ms 376 KB
#include "bulb.h"
using namespace std;
vector<int> L, R;
int win[300010], chk[300010];
int ww[300010], cc[300010];
int N;
void f(int lev)
{
	chk[lev]=1;
	if (L[lev]>=0) {
		if (chk[L[lev]]) win[lev]=win[L[lev]];
		else {
			f(L[lev]);
			win[lev]=win[L[lev]];
		}
	}
	else win[lev]=L[lev];
	if (R[lev]>=0&&!chk[R[lev]]) f(R[lev]);
}
int ff(int lev)
{
	if (cc[lev]) return ww[lev];
	cc[lev]=1;
	if (R[lev]>=0) ff(R[lev]);
	if (L[lev]==-1&&!(R[lev]==-1||win[R[lev]]==-1)) return 0;
	else if (L[lev]<0) return ww[lev]=1;
	else {
		if (!cc[L[lev]]) ff(L[lev]);
		if (ww[L[lev]]) return ww[lev]=1;
	}
	return 0;
}
int FindWinner(int T, vector<int> l, vector<int> r){
	N = L.size();
	for (int i:l) L.push_back(i);
	for (int i:r) R.push_back(i);
	f(0);
	if (win[0]==-2) return 0;
	ff(0);
	for (int i=0; i>=0; i=L[i]) {
		if (R[i]<0||(R[i]>=0&&ww[R[i]])) return 1;	
		if (R[i]==-2||(R[i]>=0&&win[R[i]]==-2)) return 0;
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct