Submission #150246

#	Time	Username	Problem	Language	Result	Execution time	Memory
150246		코딩은 체육과목입니다 (#200)	Bulb Game (FXCUP4_bulb)	C++17	0 / 100	2 ms	376 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];
bool invalid[300005];

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

    if (root != parent[root] && R[parent[root]] == 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)
                return 0;

            if (rcount[i] == 2)
            {
                int now = i;
                while (now != parent[now] && !invalid[now])
                {
                    invalid[now] = true;
                    now = parent[now];
                }
            }
        }
        
        if (R[i] == -2)
        {
            if (rcount[i] == 0 && scount[i] != N)
                return 0;

            if (rcount[i] == 1)
            {
                int now = i;
                while (now != parent[now] && !invalid[now])
                {
                    invalid[now] = true;
                    now = parent[now];
                }
            }
        }
    }

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

    return 0;

}

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