oj.uz

Submission #150686

# Submission time Handle Problem Language Result Execution time Memory
150686 2019-09-01T08:49:16 Z 맞WATLE(#3593, arnold518, ksmzzang2003, songc) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#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

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.0

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

Subtask #2
0 / 25.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 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 64.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 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -