oj.uz

Submission #149431

# Submission time Handle Problem Language Result Execution time Memory
149431 2019-09-01T06:28:12 Z mit한의대지망생(#3602, TAMREF, imeimi2000, suzy) Bulb Game (FXCUP4_bulb) C++17
11 / 100
 3 ms 476 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 3 ms 476 KB Output is correct
6 Correct 3 ms 472 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 380 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 476 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Incorrect 3 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 476 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Incorrect 3 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -