oj.uz

Submission #150535

# Submission time Handle Problem Language Result Execution time Memory
150535 2019-09-01T08:36:19 Z 채원♡예나(#3706, rhrnald, ohjw420, chris2tg) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repp(i,a) for(int i=1;i<=a;i++)
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define Fi first
#define Se second
#define INF 87654321
#define IINF 987654321987654321
#define LINF 987654321987654321
//0x3F3F3F3F3F3F3F3Fll
#define sz(v) ((int)((v).size()))
#define all(v) v.begin(),v.end()
#define pq priority_queue
#define BIGMOD 9223372036854775783
#define PI 3.14159265358979
#define eps 1e-7
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<bool,bool> pbb;
typedef pair<ll,ll> pll;
typedef complex<double> base;
typedef pair<bool,int> pbi;
typedef pair<ll,int> pli;
typedef pair<pll,ll> plll;
typedef pair<double,double> pdd;
typedef pair<int,pii> pi;

#include "bulb.h"

int FindWinner(int T,std::vector<int> L, std::vector<int> R){
	struct th{
		int a,b,d;//���,��,�ܰ�
	};
	vector<th> blues;
	queue<th> q;
	q.push({0,-1,0});
	while(!q.empty()){
		auto t=q.front();q.pop();
		if(L[t.a]>0)q.push({L[t.a],t.b,t.d+1});
		if(L[t.a]==-2){
			if(t.b==-1){
				return 0;
			}
			else blues.pb({L[t.a],t.b,t.d+1});
		}  
		if(t.b==-1){
			if(R[t.a]>0) q.push({R[t.a],t.d,t.d+1});
			else if(R[t.a]==-2){
				blues.pb({R[t.a],t.d,t.d+1});
			}
		}
	}
	sort(all(blues),[](th A,th B){return A.b<B.b;});
	if(blues.empty()) return 1;
	int exc=0,exccnt=0;
	while(exc>=0){
		exc=L[exc];
		exccnt++;
	}
	if(exccnt==L.size()){
		if(exccnt==1){
			if(L[0]==-1&&R[0]==-1) return 1;
			if(L[0]==-1&&R[0]==-2) return 1;
			if(L[0]==-2&&R[0]==-1) return 0;
			if(L[0]==-2&&R[0]==-2) return 0;
		}
		int par=0;
		while(par>=0){
			if(R[par]==-2) return 0;
			par=L[par];
		}
		return 1;
	}
	rep(i,0,blues[0].b){
		queue<th> que;
		int now=0;
		rep(j,0,i){
			now=L[now];
		}
		now=R[now];
		//printf("#%d#",now);
		que.push({now,-1,0});
		bool b=true;
		while(!que.empty()){
			auto t=que.front();que.pop();
			//printf("@%d %d %d@",t.a,L[t.a],R[t.a]);
			if(L[t.a]>0) que.push({L[t.a],t.b,t.d+1});
			if(L[t.a]==-2){
				b=false;
				break;
			}
			if(t.b==-1){
				if(R[t.a]>0) que.push({R[t.a],t.d,t.d+1});
				else if(R[t.a]==-2){
					b=false;
					break;
				}
			}
		}
		if(!b){
			continue;
		}
		else{
			return 1;
		}
	}
	return 0;
}

/*
static void my_assert(int TF, const char* message){
	if(!TF){ puts(message); exit(0); }
}

int main(){
	int N, T;
	std::vector<int> L, R;

	my_assert(scanf("%d%d", &N, &T) == 2, "Error: Invalid Input");
	my_assert(1 <= N && N <= 300000, "Error: Invalid Input");
	my_assert(1 <= T && T <= 300000, "Error: Invalid Input");

	L.resize(N), R.resize(N);
	for(int i = 0; i < N; i++){
		my_assert(scanf("%d%d", &L[i], &R[i]) == 2, "Error: Invalid Input");
		my_assert(-2 <= L[i] && L[i] <= N-1, "Error: Invalid Input");
		my_assert(-2 <= R[i] && R[i] <= N-1, "Error: Invalid Input");
	}

	int res = FindWinner(T, L, R);
	my_assert(res == 0 || res == 1, "Wrong: Wrong Answer");
	puts(res ? "Minhyung" : "Sunyoul");
	return 0;
}
*/

Compilation message

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:66:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(exccnt==L.size()){
     ~~~~~~^~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 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 292 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 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 292 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -