oj.uz

Submission #172619

# Submission time Handle Problem Language Result Execution time Memory
172619 2020-01-02T08:20:09 Z top34051 Bulb Game (FXCUP4_bulb) C++17
0 / 100
 3 ms 376 KB 
#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;

int n, T;
vector<int> L, R;
int res[maxn], lose[maxn], sumDown[maxn];

int odd, win;

void dfs(int u) {
	if(u >= n) return ;

	dfs(L[u]);
	dfs(R[u]);

	res[u] = res[L[u]];
	lose[u] = lose[L[u]] + (res[R[u]] == 0);
	sumDown[u] = sumDown[L[u]] + 1;
}

void solve(int u, int ok, int upLose, int sumUp) {
	if(u >= n) return ;

	solve(L[u], ok, upLose + (res[R[u]] == 0), sumUp + 1);
	solve(R[u], 0, upLose + (res[R[u]] == 0), sumUp + 1);
	
	if(ok) { // main line
		if(res[R[u]]) { // push to win
			odd = true;
			if(upLose == 0 && lose[R[u]] == 0) { // opponent has to win
				win = 1;
			}
		}
		else { // push to lose
			if(upLose == 0 && lose[R[u]] == 0 && sumUp + sumDown[R[u]] == n - 1) {
				win = 1;
			}
		}
	}
}

int FindWinner(int turns, vector<int> leftChild, vector<int> rightChild){
	T = turns; L = leftChild; R = rightChild; 
	n = (int)leftChild.size();

	for(auto &t : L) if(t < 0) t = n - 1 - t;
	for(auto &t : R) if(t < 0) t = n - 1 - t;

	res[n] = 1;

	dfs(0);
	solve(0, 1, 0, 0);

	if(T % 2 != 0) return odd || (sumDown[0] != n);
	if(res[0] == 0) return 0;

	return win;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -