Submission #150702

#	Time	Username	Problem	Language	Result	Execution time	Memory
150702		Ian and 2-bit memory (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	93 ms	16764 KiB

bulb

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

bool red[300055];

void dfs(int v, vector<int> &L, vector<int> &R) {
	if (v < 0) return;

	if (L[v] == -1) {
		red[v] = true;
	}

	dfs(L[v], L, R);
	dfs(R[v], L, R);

	if (L[v] >= 0) {
		red[v] |= red[L[v]];
	}
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
	int v = 0;
	vector<int> vec;

	while (v >= 0) {
		vec.push_back(v);
		v = L[v];
	}

	if (v == -2) return 0;

	dfs(0, L, R);

	vec.push_back(-1);

	for (int i = 0; i < (int)vec.size(); i++) {
		vector<int> temp;

		for (int j = 0; j <= i; j++) {
			temp.push_back(vec[j]);
		}

		if (temp.back() >= 0) {
			temp.push_back(R[temp.back()]);
		}

		while (temp.back() >= 0) {
			temp.push_back(L[temp.back()]);
		}

		if (temp.back() == -2 && temp.size() - 1 < N) continue;

		bool bad = false;

		for (int j = 0; j < (int)temp.size(); j++) {
			if (j == i) continue;
			if (temp[j] >= 0) {
				if (R[temp[j]] == -2) {
					bad = true;
					break;
				}

				if (R[temp[j]] == -1) {
					continue;
				}

				if (!red[R[temp[j]]]) {
					bad = true;
					break;
				}
			}
		}

		if (!bad) {
			return 1;
		}
	}

	return 0;
}

Compilation message (stderr)

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:52:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (temp.back() == -2 && temp.size() - 1 < N) continue;
                            ~~~~~~~~~~~~~~~~^~~

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