oj.uz

Submission #150322

# Submission time Handle Problem Language Result Execution time Memory
150322 2019-09-01T08:08:36 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#include "bulb.h"
#include <bits/stdc++.h>
using namespace std;

int wL[300005], wR[300005];
int TL[300005], TR[300005];
int l[300005], r[300005];
bool dfs(int nod, bool s){
    if(nod == -1 && s == 1) return 1;
    if(nod < 0) return 0;

    if(s == 0){
        bool ok1 = dfs(l[nod], 0);
        bool ok2 = dfs(r[nod], 1);
        return ok1 | ok2;
    }
    else{
        if(wR[nod] == -2) return 0;
        if(nod == -2) return 0;
        return dfs(l[nod], 1);
    }
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
    for(int i = 0; i < N ; ++i) l[i] = L[i], r[i] = R[i];
	for(int i = 0; i < N ; ++i) TL[i] = TR[i] = -1;

    for(int i = 0; i < N ; ++i)
        if(L[i] >= 0) TL[L[i]] = i;

    for(int i = 0; i < N ; ++i)
        if(R[i] >= 0) TR[R[i]] = i;

    for(int i = 0; i < N ; ++i){
        if(L[i] >= 0) continue ;

        int nod = i;
        wL[nod] = L[i];
        while(nod >= 0){
            wL[TL[nod]] = wL[nod];
            nod = TL[nod];
        }
    }
    for(int i = 0; i < N ; ++i){
        if(R[i] >= 0) continue ;

        int nod = i;
        wR[nod] = R[i];
        while(nod >= 0){
            wR[TR[nod]] = wL[nod];
            nod = TR[nod];
        }
    }

    if(wL[0] == -2) return 0;

    bool check = dfs(0, 0);
//
//    if(!check) return 0;

    int nod = 0, nr = 0;
    while(nod >= 0){
        if(wR[nod] == -2) ++nr;
        nod = L[nod];
    }

    if(nr > 1) return 0;

	return 1;
}

Compilation message

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:58:10: warning: unused variable 'check' [-Wunused-variable]
     bool check = dfs(0, 0);
          ^~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -