oj.uz

답안 #148007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148007 2019-08-31T11:02:14 Z imsifile Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#include "bulb.h"
using namespace std;
 
int N, dlr[303030][2], dcn, par[303030], sw[303030], qsc, cha, ch[2], valid=-1, lose[303030];
vector<int> L, R;
 
int lca(int a, int b){
	if(a==-1) return b;
	if(a==-2) return a;
	while(a>=0){
		if(dlr[a][0] <= dlr[b][0] && dlr[b][0] <= dlr[a][1]) break;
		a=par[a];
	}
	return a;
}
 
void pre(int ix){
	if(ix<0) return;
	dlr[ix][0]=dcn++;
	pre(L[ix]), pre(R[ix]);
	dlr[ix][1]=dcn-1;
}
 
void dfs(int pv, int ix){
	if(ix==-1) return;
	if(ix==-2){
		if(cha==0) valid=-2;
		if(cha==1 && qsc) valid=lca(valid,pv), lose[ch[0]]=1;
		if(cha==2) lose[ch[0]]=lose[ch[1]]=1;
		return;
	}
	par[ix]=pv;
	sw[ix]=0, qsc--;
	dfs(ix, L[ix]);
	if(cha<2) ch[cha]=ix;
	sw[ix]=1, cha++;
	dfs(ix, R[ix]);
	sw[ix]=2, cha--, qsc++;
}
 
int FindWinner(int T, std::vector<int> L_, std::vector<int> R_){
	N=L.size(), L=L_, R=R_;
	for(int i=0; i<N; i++) sw[i]=2; qsc=N;
	pre(0);
	dfs(-1, 0);
	if(valid==-2) return 0;
	if(valid==-1){
		for(int i=0; i<N; i++){
			if(!lose[i]) return 1;
		}
		return 0;
	}
	for(int i=valid; i>=0; i=par[i]){
		if(!lose[i]) return 1;
	}
	return 0;
}

Compilation message

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:43:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=0; i<N; i++) sw[i]=2; qsc=N;
  ^~~
bulb.cpp:43:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=0; i<N; i++) sw[i]=2; qsc=N;
                                  ^~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -