Submission #150686

#	Time	Username	Problem	Language	Result	Execution time	Memory
150686		맞WATLE (#200)	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	2 ms	376 KiB

bulb

#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, LC[MAXN+10], ans;
int dp1[MAXN+10], dp2[MAXN+10];
vector<int> L, R, P;

void dfs1(int now)
{
    if(L[now]<0) { LC[now]=(L[now]==-1); return; }
    else
    {
        dfs1(L[now]);
        P[L[now]]=now;
    }

    if(R[now]>=0)
    {
        dfs1(R[now]);
        P[R[now]]=now;
    }

    LC[now]=LC[L[now]];
}

void dfs2(int now)
{
    if(now==0)
    {
        if(L[now]>=0) dp1[now]=LC[L[now]];
        else dp1[now]=(L[now]==-1);
    }
    else
    {
        if(L[now]>=0) dp1[now]=dp1[P[now]]&&LC[L[now]];
        else dp1[now]=dp1[P[now]]&&(L[now]==-1);
    }

    if(L[now]>=0) dfs2(L[now]);
    if(R[now]>=0) dfs2(R[now]);

    if(L[now]<0)
    {
        dp2[now]=LC[now];
    }
    else
    {
        dp2[now]=LC[now]&&dp2[L[now]];
    }
}

void dfs3(int now)
{
    if(L[now]>=0) dfs3(L[now]);
    if(R[now]>=0) dfs3(R[now]);

    if(R[now]>=0) ans|=dp1[now]&&dp2[R[now]];
    else ans|=dp1[now];
}

int FindWinner(int _T, vector<int> _L, vector<int> _R)
{
    int i, j;
    L=_L; R=_R; N=L.size(); P.resize(N);

    dfs1(0);
    if(LC[0]==-2) return 0;
    dfs2(0);
    dfs3(0);
    return ans;
}

Compilation message (stderr)

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:70:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
bulb.cpp:70:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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