Submission #149394

#	Time	Username	Problem	Language	Result	Execution time	Memory
149394		1 WA = 5 Push Up (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	94 ms	10032 KiB

bulb

#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;

int T;
vector <int> L, R;

int col[300010];
bool able[300010];
bool dummy;

void sub_tree(int x)
{
	if (L[x] >= 0) sub_tree(L[x]);
	if (R[x] >= 0) dummy = true, sub_tree(R[x]);

	col[x] = L[x] >= 0 ? col[L[x]] : L[x];
	
	able[x] = L[x] >= 0 ? able[L[x]] : false;
	if (R[x] == -2 || (R[x] >= 0 && col[R[x]] == -2)) able[x] = true;

	if (L[x] == -1 || (L[x] >= 0 && col[L[x]] == -1))
		if (R[x] == -1 || (R[x] >= 0 && col[R[x]] == -1))
			dummy = true;
}

bool main_line(int x)
{
	if (R[x] < 0) return true;
	
	sub_tree(R[x]);
	if (!able[R[x]]) return true;
	if (col[R[x]] == -2) return false;

	if (L[x] < 0) return dummy;
	return main_line(L[x]);
}

int FindWinner(int T_, std::vector<int> L_, std::vector<int> R_) {
	T = T_;
	L = L_; R = R_;

	int N = L.size();

	int x;
	for (x = 0; x >= 0; x = L[x]);
	if (x == -2) return 0;

	if (main_line(0)) return 1;
	return 0;
}

Compilation message (stderr)

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:43:6: warning: unused variable 'N' [-Wunused-variable]
  int N = L.size();
      ^

• Subtask 1: 11 / 11
• Subtask 2: 25 / 25
• Subtask 3: 64 / 64