Submission #150418

#	Time	Username	Problem	Language	Result	Execution time	Memory
150418		코딩은 체육과목입니다 (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	110 ms	21500 KiB

bulb

#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];
int 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 (parent[root] != -1 && 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);
}

void revdfs(int root, vector<int>& L, vector<int>& R)
{
    if (L[root] >= 0)
    {
        revdfs(L[root], L, R);
        rev[root] += rev[L[root]];
    }

    if (R[root] >= 0)
    {
        revdfs(R[root], L, R);
        rev[root] += rev[R[root]];
    }
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
    memset(parent, -1, sizeof(parent));

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

        if (R[i] >= 0)
            parent[R[i]] = i;
    }

    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;
                rev[i]++;
            }

            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++;
                rev[i]++;
            }

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

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

    revdfs(0, L, R);

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

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

    return 0;

}

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