oj.uz

Submission #150657

# Submission time Handle Problem Language Result Execution time Memory
150657 2019-09-01T08:47:29 Z Ian and 2-bit memory(#3648, percywtc, nhho, ulna) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#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);

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

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

		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

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

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 256 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
2 Correct 2 ms 256 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 -