#include "bulb.h"
#include<algorithm>
using namespace std;
int n;
int parent[600009];
int value[600009];
int m;
int root;
int res;
vector<int> a;
vector<int> b;
vector<int> w;
void dfs(int si, int sum)
{
if (si >= n) {
if (value[si] == -1)
{
value[si] = sum;
}
return;
}
dfs(a[si], sum);
dfs(b[si], sum + 1);
value[si] = min(value[a[si]], value[b[si]]);
}
void dfs2(int si)
{
if (si >= n) {
return;
}
dfs2(a[si]);
dfs2(b[si]);
value[si] = min(value[a[si]], value[b[si]]);
}
void add_naive(int si, int val) {
if (si >= n) {
value[si] += val;
return;
}
add_naive(a[si], val);
add_naive(b[si], val);
value[si] = min(value[a[si]], value[b[si]]);
}
void flip_naive(int si, int type) {
if (type == 0) {
add_naive(a[si], 1);
add_naive(b[si], -1);
}
else {
add_naive(a[si], -1);
add_naive(b[si], 1);
}
}
void dfs_type2(int si)
{
if (si >= n)return;
if (value[b[si]] > 2) { res = 1; return; }
dfs_type2(b[si]);
if (res == 1)return;
dfs_type2(a[si]);
}
void precal(int si) {
if (si >= n)return;
if (value[a[si]] == 1) {
w.push_back(si);
return;
}
if(value[b[si]] == 1)
precal(b[si]);
}
void deepdark(int si, int wi)
{
if (si >= n)return;
if (si != wi)
{
if (b[si] < n) {
res = 0;
return;
}
deepdark(a[si], wi);
}
else {
if (a[si] < n)
{
res = 0;
return;
}
deepdark(b[si], wi);
}
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
n = L.size();
a = L;
b = R;
m = n;
int i, j, k;
for (i = 0; i < n; i++) {
parent[i] = i;
}
for (i = 0; i < n; i++) {
if (L[i] >= 0)
{
parent[L[i]] = i;
}
else {
if (L[i] == -1)
value[m] = 999999;
else
value[m] = -1;
a[i] = m;
parent[m] = i;
m++;
}
if (R[i] >= 0)
{
parent[R[i]] = i;
}
else {
if (R[i] == -1)
value[m] = 999999;
else
value[m] = -1;
b[i] = m;
parent[m] = i;
m++;
}
}
for (i = 0; i < n; i++) { if (parent[i] == i)break; }
root = i;
res = 0;
dfs(root, 0);
if (value[root] == 0) return 0;
if (n <= 100) {
for (i = 0; i < n; i++) {
flip_naive(i, 0);
for (j = 0; j < n; j++) {
if (i == j) { flip_naive(j, 1); }
else { flip_naive(j, 0); }
dfs2(root);
bool nono = false;
if (value[root] == 0) nono = true;
if (i == j) { flip_naive(j, 0); }
else { flip_naive(j, 1); }
if (nono)break;
}
flip_naive(i, 1);
if (j == n) {
//printf("%d is answer\n", i);
break;
}
}
return (i < n);
}
if (value[root] > 2)return 1;
else if (value[root] == 2) {
dfs_type2(root);
}
else {
while (root < n)
{
precal(root);
if (w.size() > 0)
{
flip_naive(w[0], 0);
dfs2(root);
// printf("%d --> %d\n", w[0], value[root]);
if (value[root] == 1) res = 0;
else if (value[root] >= 2) res = 1;
else {
res = 1;
deepdark(root, w[0]);
}
if (res == 1)
break;
flip_naive(w[0], 1);
}
root = a[root];
}
}
return res;
}
Compilation message
bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:96:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
