oj.uz

Submission #172643

# Submission time Handle Problem Language Result Execution time Memory
172643 2020-01-02T09:08:26 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, even, 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;

	printf("%d: %d %d %d\n",u,res[u],lose[u],sumDown[u]);
}

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 = 1;
			if(upLose == 0 && lose[R[u]] == 0) { // opponent has to win
				win = 1;
			}
		}
		else { // push to lose
			even = 1;
			if(upLose == 0 && lose[R[u]] == 0 && sumUp + sumDown[R[u]] + 1 == n) {
				win = 1;
			}
		}
	}
}

int CNT = 0;

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

	CNT++;
	assert(CNT == 1);

	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) {
		// if(res[0] == 1 && sumDown[0] != n) return 1;
		if(odd) return 1;
		return 0; 
	}

	if(res[0] == 0) return 0;

	if(sumDown[0] != n && even == 0) return 1;

	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 -