Submission #150685

#	Time	Username	Problem	Language	Result	Execution time	Memory
150685		본인 방금 올솔하는 상상함 (#200)	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	2 ms	376 KiB

bulb

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

using namespace std;

int ok[N], is[N];
int unsafe[N];
int parent[N];
vector<int> l, r;
vector<int> ll, rr;
int n;
bool isLinear;

/*
void dfs(int i, bool hasUncle){
	if(l[i]>=0) dfs(l[i], hasUncle||(r[i]>=0));
	if(r[i]>=0) dfs(r[i], hasUncle||(l[i]>=0));
	if(r[i]==-2||) frag[i]=(l[i]<=0||frag[l[i]]);

	if(l[i]==-2) is[i]=1;
	else if(l[i]>=0) is[i]=is[l[i]];

	if(r[i]==-2) ok[i]=1;
	else if(r[i]>=0) ok[i]=is[r[i]];
	if((l[i]==-2||(l[i]>=0&&is[l[i]]))&&(!isLinear||r[i]>=0)) ok[i]=1;
	if(l[i]>=0) ok[i]|=ok[l[i]];

	if(l[i]<0){
		
	}
	if(rok[l[i]]==0&&isLinear){
		
	}
	else if(rok[l[i]]==0){
		if(r[i]==-2) rok[i]=1;
		else if(r[i]==-1) rok[i]=0;
		else if(is[r[i]]) rok[i]=is[l[i]]||ok[r[i]];
		else if(hasUncle||!frag[r[i]]) rok[i]=0;
	}
	else{
		rok[i]=is[l[i]]||((r[i]<=0&&r[i]==-2&&!isLinear)||ok[r[i]]);
	}
}

void checkLinear(int i){
	if(l[i]>=0&&r[i]>=0){
		isLinear=0;
		return;
	}
	if(l[i]>=0) checkLinear(l[i]);
	if(r[i]>=0) checkLinear(r[i]);
}
*/

void dfs(int i){
	if(l[i]<0) ll[i]=l[i];
	else l[i]=ll[l[i]];
	if(r[i]<0) rr[i]=r[i];
	else r[i]=ll[r[i]];
	if(l[i]>=0) ok[i]|=ok[l[i]];
	if((r[i]<0&&r[i]==-2)||(r[i]>=0&&ll[r[i]]==-2)) ok[i]=1;

	if(l[i]>=0&&unsafe[l[i]]) unsafe[i]=1;
	if(rr[i]==-2) unsafe[i]=1;
}

int FindWinner(int T, vector<int> L, vector<int> R){
	l=L;
	r=R;
	n = L.size();
	ll.resize(n);
	rr.resize(n);
	for(int i=0;i<n;i++) parent[i]=i;
	for(int i=0;i<n;i++){
		if(l[i]>=0) parent[l[i]]=i;
		if(r[i]>=0) parent[r[i]]=i;
	}
	int root=0;
	for(int i=0;i<n;i++) if(parent[i]!=i) root=i;
	dfs(root);
	int flag=1;
	if(ll[root]==-2){
		return 0;
	}
	int fst=-1;
	for(int i=root;i>=0;i=l[i]){
		if(rr[i]==-2){
			fst=i;
			break;
		}
	}
	if(fst>=0){
		for(int i=root;i!=fst;i=l[i]){
			if(r[i]>=0&&!ok[r[i]]) return 1;
			else if(r[i]==-1) return 1;
		}
		return 0;
	}
	else{
		int c=0;
		for(int i=root;i>=0;i=l[i]){
			if(r[i]>=0&&!ok[r[i]]) return 1;
			else if(r[i]==-1) return 1;
		}
		for(int i=root;i>=0;i=l[i]){
			if(!unsafe[r[i]]) return 1;
		}
		return 0;
	}
	/*
	for(int i=0;i<n;i++) parent[i]=i;
	for(int i=0;i<n;i++){
		if(l[i]>=0) parent[l[i]]=i;
		if(r[i]>=0) parent[r[i]]=i;
	}
	int root=0;
	for(int i=0;i<n;i++) if(parent[i]!=i) root=i;
	isLinear=1;
	checkLinear(root);
	dfs(root);
	if(rok[root]) return 0;
	return 1;
	*/
	/*
	int flag=1;
	for(int i=root;i>=0;i=l[i]){
		if(is[i]){
			flag=0;
			break;
		}
	}
	if(flag) return 1;
	for(int i=root;i>=0;i=l[i]){
		if(r[i]>=0&&)
		if(is[i]) break;
	}*/
}

Compilation message (stderr)

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:101:7: warning: unused variable 'c' [-Wunused-variable]
   int c=0;
       ^
bulb.cpp:82:6: warning: unused variable 'flag' [-Wunused-variable]
  int flag=1;
      ^~~~

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