Submission #154296

#	Time	Username	Problem	Language	Result	Execution time	Memory
154296		andreiomd	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	113 ms	9092 KiB

bulb

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

using namespace std;

const int NMAX = 3e5 + 5;

vector < int > Left, Right;

int N;

int FindWinner(int T, std :: vector < int > L, std :: vector < int > R)
{
    Left = L;
    Right = R;

    N = (int)L.size();

    int Node = 0;

    while(Node >= 0)
        Node = Left[Node];

    if(Node == -2) /// The leftest bulb is blue;
        return 0;

    for(int i = 0; i < N; ++i)
    {
        bool Red = true;
        bool Ok = false; /// Daca alegem apasarea unui intrerupator, iar in partea opusa directiei curentului, exista subarbore;

        Node = 0;

        while(Node >= 0)
        {
            if(Node == i)
            {
                if(Left[Node] >= 0)
                    Ok = true;
            }
            else
            {
                if(Right[Node] >= 0)
                    Ok = true;
            }

            int Go = (Node == i) ? Left[Node] : Right[Node];

            while(Go >= 0)
                Go = (Go == i) ? Right[Go] : Left[Go];

            if(Go == -2)
            {
                Red = false;

                break;
            }

            if(Node == i) /// The "i" - th switch is pressed;
                Node = Right[Node];
            else Node = Left[Node];
        }

        if(Red && (!Ok || Node == -1)) /// One red bulb is turned on;
            return 1;
    }

    return 0;
}

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