Submission #149411

#	Time	Username	Problem	Language	Result	Execution time	Memory
149411		Cafe Maru (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	144 ms	24540 KiB

bulb

#include "bulb.h"

const int RED = -1;
const int BLUE = -2;

using vi = std::vector<int>;

const int NMAX = 300000;

bool c[NMAX*4+3];
void SetTrue(int nl,int nr,int l,int r,int node){
    if(l<=nl&&nr<=r){
        c[node]=true; return;
    }
    else if(nr<l||r<nl) return;
    int mid = (nl+nr)/2;
    SetTrue(nl,mid,l,r,node*2+1);
    SetTrue(mid+1,nr,l,r,node*2+2);
}
int N;
void SetTrue(int l,int r){if(l<=r) SetTrue(0,N-1,l,r,0);}
bool ReadBool(int nl,int nr,int x,int node){
    if(c[node]) return true;
    if(nl==nr) return c[node];
    int mid = (nl+nr)/2;
    if(x<=mid) return ReadBool(nl,mid,x,node*2+1);
    else return ReadBool(mid+1,nr,x,node*2+2);
}
bool ReadBool(int x){return ReadBool(0,N-1,x,0);}

bool hasTwo[NMAX];
int L[NMAX], R[NMAX];
int reorder[NMAX];

int tc;
void ReorderDfs(const vi& _L, const vi& _R, int root=0){
    int reroot = reorder[root];
    if(_L[root] >= 0){
        reorder[_L[root]] = ++tc;
        L[reroot] = tc;
        ReorderDfs(_L, _R, _L[root]);
    }
    else{
        L[reroot] = _L[root];
    }
    if(_R[root] >= 0){
        reorder[_R[root]] = ++tc;
        R[reroot] = tc;
        ReorderDfs(_L, _R, _R[root]);
    }
    else{
        R[reroot] = _R[root];
    }
}

void FindTwo(int root, vi& rv){
    if(L[root]>=0) FindTwo(L[root], rv);
    else if(rv.size()==2 && L[root]==BLUE){
        hasTwo[rv[0]] = hasTwo[rv[1]] = true;
    }

    if(rv.size() < 2){
        rv.push_back(root);
        if(R[root]>=0) FindTwo(R[root], rv);
        else if(rv.size()==2 && R[root] == BLUE){
            hasTwo[rv[0]] = hasTwo[rv[1]] = true;
        }
        rv.pop_back();
    }
}

void FindOne(){
    int st = 0;
    int it = 0;
    while(1){
        if(R[it]==BLUE){
            SetTrue(it+1,N-1);
        }
        else if(R[it]>=0){
            int st2 = R[it];
            int it2 = st2;
            while(L[it2]>=0) it2 = L[it2];
            if(L[it2]==BLUE){
                SetTrue(it+1, st2-1);
                SetTrue(it2+1, N-1);
            }
        }
        if(L[it]>=0) it = L[it];
        else return;
    }
}

int FindWinner(int T, std::vector<int> _L, std::vector<int> _R){
    N = _L.size();

    int it=0;
    while(_L[it]>=0) it = _L[it];
    if(_L[it]==BLUE) return 0;

    ReorderDfs(_L, _R);
    FindOne();
    vi rv;
    FindTwo(0, rv);

    for(int i=0;i<N;i++){
        if(hasTwo[i]) continue;
        if(ReadBool(i)) continue;

        return 1;
    }
    return 0;
}

Compilation message (stderr)

bulb.cpp: In function 'void FindOne()':
bulb.cpp:73:9: warning: unused variable 'st' [-Wunused-variable]
     int st = 0;
         ^~

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