oj.uz

Submission #172652

# Submission time Handle Problem Language Result Execution time Memory
172652 2020-01-02T09:33:11 Z top34051 Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 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
			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(res[0] == 0) return 0;
	return win;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 64.0

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