Submission #149425

#	Time	Username	Problem	Language	Result	Execution time	Memory
149425		CHT를 사랑하는 모임 (#200)	Bulb Game (FXCUP4_bulb)	C++17	11 / 100	2 ms	420 KiB

bulb

#include "bulb.h"
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 300010;

int l[MAX_N+1], r[MAX_N+1];
int N, T;
int l2[MAX_N+1];
int r2[MAX_N+1];
bool dp1[MAX_N+1];
bool dp2[MAX_N+1];

int num = 0;

void dfs(int x){
	if(r[x]>=0){
		dfs(r[x]);
		r2[x] = l2[r[x]];
	}else{
		r2[x] = -r[x];
	}
	if(l[x]>=0){
		dfs(l[x]);
		l2[x] = l2[l[x]];
		dp1[x] = (dp1[l[x]] && (r2[x]==1)); 
		dp2[x] = (dp2[l[x]] || (r2[x]==1));
	}else{
		l2[x] = -l[x];
		dp1[x] = (r2[x]==1);
		dp2[x] = (r2[x]==1 || l2[x]==1);
	}
}

bool dfs2(int x){
	if(r[x]>=0){
		if(dp1[r[x]] && (r2[x]==1)){
			return true;
		}
	}else{
		if(r2[x]==1){
			return true;
		}
	}
	if(r2[x]==1 &&  l[x]>=0){
		return dfs2(l[x]);
	}
	return false;
}

int FindWinner(int t, vector<int> L, vector<int> R){
	N = R.size(); T = t;
	for(int i=0; i<N; i++){
		l[i] = L[i]; r[i] = R[i];
	}
	dfs(0);
	if(l2[0]==2){
		return 0;
	}
	int idx = 0;
	while(1){
		num++;
		if(L[idx]<0){
			break;
		}
		idx = L[idx];
	}
	idx = 0;
	bool tf = true;
	int cnt = 1;
	while(1){
		if(R[idx]<0){
			if(R[idx]!=-1){
				tf = false;
			}
		}else{
			if(r2[idx]!=1){
				if(dp2[r[idx]]){
					cnt--;
					if(cnt<0){
						tf = false;
					}
				}else{
					tf = false;
				}
			}
		}
		if(L[idx]<0){
			break;
		}
		idx = L[idx];
	}
	if(tf)	return true;
	if(dp1[0] && (num!=N)){
		return true;
	}
	bool b = dfs2(0);
	return b;
}

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