oj.uz

답안 #150860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150860 2019-09-01T08:59:57 Z 이 대회 미분 되나요?(#3668, wookje, edenooo, jms100300) Bulb Game (FXCUP4_bulb) C++17
11 / 100
 2 ms 380 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 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 380 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 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -