#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()){
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(t.b!=-1&&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()){
~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
364 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
