Submission #148888

#	Time	Username	Problem	Language	Result	Execution time	Memory
148888		USA1 (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	103 ms	18688 KiB

bulb

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

using namespace std;
const int MAXN = 300100;

int N;
int L[MAXN], R[MAXN];
vector <int> vs;
vector <int> hs;
int llim;
bool bbad[MAXN], hbad[MAXN];
bool bfull;
int nc[MAXN];

void flood (int cloc, int cdep)
{
    nc[cloc] = vs.size();
    if (cloc < 0)
    {
        if (cloc == -2)
        {
            if (vs.size() > 2)
                return;
            if (vs.size() == 0)
            {
                // gg
                llim = -100;
            }
            else if (vs.size() == 1)
            {
                // can't intercept after, or at unless this is the full path
                if (cdep == N)
                {
                    // must go at or before here
                    llim = min (llim, vs[0]);
                }
                else
                {
                    // must go before here
                    llim = min (llim, vs[0] - 1);
                }
            }
            else
            {
                int lo = hs[0], hi = hs[1];
                hbad[lo] = hbad[hi] = true;
            }
        }
        return;
    }

    flood (L[cloc], cdep + 1);
    vs.push_back(cdep);
    hs.push_back(cloc);
    flood (R[cloc], cdep + 1);
    vs.pop_back();
    hs.pop_back();
}

int FindWinner(int T, std::vector<int> vl, std::vector<int> vr){
    N = vl.size();
    for (int i = 0; i < N; i++)
    {
        L[i] = vl[i];
        R[i] = vr[i];
    }

    for (int i = 0; i < MAXN; i++)
    {
        bbad[i] = hbad[i] = false;
        nc[i] = 0;
    }
    for (int i = 0; i < N; i++)
    {
        L[i] = vl[i];
        R[i] = vr[i];
    }

    llim = 1e9;
    flood (0, 0);

    int cloc = 0, cdep = 0;
    while (cloc >= 0)
    {
        if (!hbad[cloc] && cdep <= llim)
            return 1;
        cloc = L[cloc];
        cdep++;
    }

    if (llim < 1e6)
        return 0;

    for (int i = 0; i < N; i++)
        if (nc[i] >= 2 && !hbad[i])
            return 1;
    return 0;
}

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