Submission #150860

#	Time	Username	Problem	Language	Result	Execution time	Memory
150860		이 대회 미분 되나요? (#200)	Bulb Game (FXCUP4_bulb)	C++17	11 / 100	2 ms	380 KiB

bulb

#include "bulb.h"
#include<vector>
#include<algorithm>
using namespace std;

#define REDWIN 1
#define BLUEWIN 0
#define RED -1
#define BLUE -2

int N, ty1, ty2;
vector<int> l, r;
int dp[300301], dp1[300301][2], dp2[300301][2];
int res = 0;

int goLeft(int n)
{
	if (dp[n] != 0) return dp[n];
	if (l[n] >= 0) return dp[n] = goLeft(l[n]);
	return dp[n] = l[n];
}

int moveOne(int n, int c) //�� �� �������� �� RED�� �� �� �ִ°�?
{
	if (n < 0) return n;
	if (dp1[n][c]) return dp1[n][c];

	int r1 = BLUE, r2 = BLUE;
	if (c) r1 = moveOne(r[n], 0);
	r2 = moveOne(l[n], c);
	if (r1 == RED || r2 == RED) return dp1[n][c] = RED;
	return dp1[n][c] = BLUE;
}

int allRed(int n, int c)
{
	if (n < 0) return n;
	if (dp2[n][c]) return dp2[n][c];

	int r1 = RED, r2 = RED;
	if (c) r1 = allRed(r[n], 0);
	r2 = allRed(l[n], c);
	if (r1 == BLUE || r2 == BLUE) return dp2[n][c] = BLUE;
	return dp2[n][c] = RED;
}

void DFS(int n)
{
	if (n < 0) return;

	if (r[n] == BLUE) ty2++;
	else if (goLeft(r[n]) == BLUE)
	{
		if (moveOne(r[n], 1) == BLUE) ty2++;
		else ty1++;
	}

	DFS(l[n]);
}

void DFS2(int n)
{
	if (n < 0) return;

	if (goLeft(n) == RED && allRed(r[n], 1) == RED) res = 1;

	DFS2(l[n]);
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	N = L.size(); l = L; r = R;
	if (goLeft(0) == BLUE) return BLUEWIN;
	moveOne(0, 1);
	DFS(0);
	if (ty2 == 0 && ty1 <= 1) return REDWIN;

	DFS2(0);
	if (res == 1) return REDWIN;
	
	return BLUEWIN;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 25
• Subtask 3: 0 / 64