Submission #149431

#	Time	Username	Problem	Language	Result	Execution time	Memory
149431		mit한의대지망생 (#200)	Bulb Game (FXCUP4_bulb)	C++17	11 / 100	3 ms	476 KiB

bulb

#include "bulb.h"
#include <vector>

using namespace std;

vector<int> L, R;

int n;
bool vis[300001];
bool chB[300001];
bool res[300001];
int D[300001];
int U[300001];
bool BD[300001];
bool BU[300001];
bool inZ[300001];

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = 1;
    if (L[x] < 0) {
        res[x] = L[x] == -2;
    }
    else {
        dfs(L[x]);
        res[x] = res[L[x]];
    }
    if (R[x] < 0) {
        chB[x] = R[x] == -2;
    }
    else {
        dfs(R[x]);
        chB[x] = res[R[x]];
    }
}

void dfs2(int x) {
    if (vis[x]) return;
    vis[x] = 1;
    D[x] = 1;
    bool B;
    if (R[x] < 0) {
        B = R[x] == -2;
    }
    else {
        dfs2(R[x]);
        B = res[R[x]];
    }
    BD[x] = B;
    if (L[x] < 0) {
    }
    else {
        U[L[x]] = U[x] + 1;
        BU[L[x]] = BU[x] || B;
        dfs2(L[x]);
        BD[x] |= BD[L[x]];
        D[x] += D[L[x]];
    }
    if (inZ[x]) {
        int UD = U[x] + 1;
        int Rres = R[x];
        bool pos = 1;
        if (BU[R[x]]) pos = 0;
        if (R[x] >= 0) {
            UD += D[R[x]];
            Rres = res[R[x]];
            if (BD[R[x]]) pos = 0;
        }
        if (UD < n && Rres) pos = 0;
        if (pos) throw true;
    }
}

int FindWinner(int T, vector<int> _L, vector<int> _R) {
    n = _L.size();
    L = _L;
    R = _R;
    int UD = 0;
    for (int i = 0; i >= 0; i = L[i]) inZ[i] = 1, ++UD;
    for (int i = 0; i < n; ++i) vis[i] = 0;
    dfs(0);
    for (int i = 0; i < n; ++i) vis[i] = 0;
    U[0] = 0;
    try {
        dfs2(0);
        if (UD < n && !BD[0]) throw true;
        throw false;    
    } catch (bool b) {
        return b;
    }
    return -1;
}

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