Submission #150498

#	Time	Username	Problem	Language	Result	Execution time	Memory
150498		ProofByTLE (#200)	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	2 ms	376 KiB

bulb

#include "bulb.h"

// Standard libraries
#include <stdio.h>
#include <vector>

// Global attributes
int N; // size
std::vector<int> left_ancestor_destination;
std::vector<int> leftchild, rightchild; // red -1 blue -2
std::vector<bool> perfect_red; // is this group perfect red?
std::vector<bool> final_left_red; // is this group's destination red?

// Set ancestor destination, perfect_red and final_left_red.
// Assuming all switches are left.
void set_left_ancestor_destinations(int now){

	if(leftchild[now] >= 0){
		left_ancestor_destination[leftchild[now]] = left_ancestor_destination[now];
		set_left_ancestor_destinations(leftchild[now]);
	}
	else{
		final_left_red[left_ancestor_destination[now]] = (leftchild[now] == -1);
		if(leftchild[now] == -2) perfect_red[left_ancestor_destination[now]] = false;
	}

	if(rightchild[now] >= 0){
		left_ancestor_destination[rightchild[now]] = rightchild[now];
		set_left_ancestor_destinations(rightchild[now]);
		if(!final_left_red[rightchild[now]]) // If this route leads to blue
			perfect_red[left_ancestor_destination[now]] = false;
	}
	else{
		if(rightchild[now] == -2) perfect_red[left_ancestor_destination[now]] = false;
	}
}

// Solver function
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	N = L.size(); // size

	// Switches
	leftchild = L, rightchild = R;
	perfect_red.resize(N, true);

	// Set left ancestor destination
	left_ancestor_destination.resize(N, -1);
	perfect_red.resize(N, true);
	final_left_red.resize(N, true);
	left_ancestor_destination[0] = 0;
	set_left_ancestor_destinations(0);

	// Debug
	/*printf("Set attributes using DFS.\n");
	for(int i=0; i<N; i++){
		printf("Node %d: left ancestor %d, leftchild %d, rightchild %d\n",
			i, left_ancestor_destination[i], leftchild[i], rightchild[i]);
		if(left_ancestor_destination[i] == i){
			printf("\t[Boss] final left red %c, perfect red %c\n", 
				final_left_red[i] ? 'T':'F', perfect_red[i] ? 'T': 'F');
		}
	} fflush(stdout);*/

	// Always impossible
	if(!final_left_red[0]) return false;
	
	// Search on changing
	int now = 0;
	bool right_are_reds_so_far = true;
	while(now >= 0 && right_are_reds_so_far){

		// 0 -> .. (leftslide) .. -> now --R-> rightchild -> .. (leftslide) -> leaf ?
		if(rightchild[now] >= 0){
			if(perfect_red[rightchild[now]]) return true;
		}

		// Right are reds so far?
		if(rightchild[now] >= 0){
			if(!final_left_red[rightchild[now]]) right_are_reds_so_far = false;
		}
		else if(rightchild[now] == -2) right_are_reds_so_far = false;

		// Go next step
		now = leftchild[now];
	} 
	
	// Last chance: Can we do outside-movement?
	if(perfect_red[0]){

	}

	// No way
	return false;
}

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