oj.uz

Submission #150341

# Submission time Handle Problem Language Result Execution time Memory
150341 2019-09-01T08:10:48 Z 코딩은 체육과목입니다(#3561, jwvg0425, 16silver, jhuni) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#include "bulb.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int parent[300005];
int rcount[300005];
int scount[300005];
int rparent[300005]; // ���� ����� R child parent
bool invalid[300005];
bool rev[300005];
int c = 0;
ii rs[300005];


void dfs(int root, vector<int>& L, vector<int>& R)
{
    rcount[root] = rcount[parent[root]];
    rparent[root] = rparent[parent[root]];
    scount[root] = scount[parent[root]] + 1;

    if (root != parent[root] && R[parent[root]] == root)
    {
        rparent[root] = parent[root];
        rcount[root]++;
    }

    if (L[root] >= 0)
        dfs(L[root], L, R);

    if (R[root] >= 0)
        dfs(R[root], L, R);
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();

    dfs(0, L, R);

    for (int i = 0; i < N; i++)
    {
        if (L[i] == -2)
        {
            if (rcount[i] == 0)
                return 0;

            if (rcount[i] == 1 && scount[i] != N)
            {
                c++;
                invalid[rparent[i]] = true;
                int now = i;
                
                while (!rev[now] && now != parent[now])
                {
                    rev[now] = true;
                    now = parent[now];
                }
            }

            if (rcount[i] == 2)
            {
                int ra = rparent[i];
                int rb = rparent[ra];

                invalid[ra] = invalid[rb] = true;
            }
        }
        
        if (R[i] == -2)
        {
            if (rcount[i] == 0 && scount[i] != N)
            {
                c++;
                invalid[i] = true;
                int now = i;

                while (!rev[now] && now != parent[now])
                {
                    rev[now] = true;
                    now = parent[now];
                }
            }

            if (rcount[i] == 1)
            {
                int ra = rparent[i];

                invalid[ra] = invalid[i] = true;
            }
        }
    }

    if (c > 0)
    {
        for (int i = 0; i < N; i++)
        {
            if (!rev[i])
                invalid[i] = true;
        }
    }

    for (int i = 0; i < N; i++)
    {
        if (!invalid[i])
            return 1;
    }

    return 0;

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 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 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 #3
0 / 64.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 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -