oj.uz

Submission #150975

# Submission time Handle Problem Language Result Execution time Memory
150975 2019-09-01T13:32:01 Z dennisstar Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 396 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&&!cc[R[lev]]) ff(R[lev]);
	if (R[lev]==-2||(R[lev]>=0&&win[R[lev]]==-2)) return 0;
	if (L[lev]<0||(L[lev]>=0&&ff(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;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Incorrect 2 ms 348 KB Output isn't correct
3 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 396 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 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 396 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -