#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) //�� �� �������� �� BLUE�� �� ���°�?
{
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 && (r[n] == RED || (r[n] != BLUE && 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) return REDWIN;
return BLUEWIN;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
404 KB |
Output is correct |
3 |
Correct |
2 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
348 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 |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
348 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 |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |