Submission #150625

#	Time	Username	Problem	Language	Result	Execution time	Memory
150625		ummm (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	121 ms	17328 KiB

bulb

/* cerberus97 - Hanit Banga */

#include "bulb.h"
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 3e5 + 10;

vector<int> l, r, turns;
bool p2wins = false;
bool extra = false;
bool t1 = false;
bool del[N], del2[N], on_path[N];

void dfs(int u);

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int n = L.size();
	l = L; r = R;
	dfs(0);
	if (p2wins) {
		return false;
	}
	if (t1) {
		for (int i = 0; i < n; ++i) {
			if (!on_path[i]) {
				del[i] = true;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (del[i]) {
			continue;
		} else if (del2[i] and extra) {
			continue;
		} else {
			return true;
		}

	}
	return false;
}

void dfs(int u) {
	if (u == -1) {
		return;
	} else if (u == -2) {
		if (turns.empty()) {
			p2wins = true;
		} else if (turns.size() == 2) {
			del[turns[0]] = true;
			del[turns[1]] = true;
		} else if (turns.size() == 1) {
			del2[turns[0]] = true;
			t1 = true;
		}
	} else {
		on_path[u] = (turns.empty());
		if (!turns.empty()) {
			extra = true;
		}
		dfs(l[u]);
		turns.pb(u);
		dfs(r[u]);
		turns.pop_back();
	}
}

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