제출 #290919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290919		Kastanda	장난감 기차 (IOI17_train)	C++11	100 / 100	624 ms	1900 KiB

train

// M
#include<bits/stdc++.h>
#include "train.h"
using namespace std;
const int N = 5005;
int n, m, A[N], R[N], Z[N], F[N], D[N];
vector < int > in[N], out[N];

vector < int > who_wins(vector < int > _A, vector < int > _R, vector < int > _U, vector < int > _V)
{
        n = (int)_A.size();
        m = (int)_U.size();
        for (int i = 0; i < n; i ++)
                A[i] = _A[i];
        for (int i = 0; i < n; i ++)
                R[i] = _R[i];
        for (int i = 0; i < m; i ++)
        {
                out[_U[i]].push_back(_V[i]);
                in[_V[i]].push_back(_U[i]);
        }


        for (int __ = 0;; __ ++)
        {
                queue < int > qu;
                memset(D, 0, sizeof(D));
                memset(Z, 0, sizeof(Z));
                for (int i = 0; i < n; i ++)
                        if (R[i] && !F[i])
                                Z[i] = 1, qu.push(i);
                while (qu.size())
                {
                        int v = qu.front();
                        qu.pop();
                        for (int u : in[v])
                                if (!Z[u] && !F[u])
                                {
                                        if (A[u])
                                                Z[u] = 1, qu.push(u);
                                        else
                                        {
                                                D[u] ++;
                                                if (D[u] == (int)out[u].size())
                                                        Z[u] = 1, qu.push(u);
                                        }
                                }
                }

                memset(D, 0, sizeof(D));
                bool yodeloohoo = 0;
                for (int i = 0; i < n; i ++)
                        if (!Z[i] && !F[i])
                                F[i] = 1, yodeloohoo = 1;
                if (!yodeloohoo)
                        break;
                for (int i = 0; i < n; i ++)
                        if (F[i]) qu.push(i);
                while (qu.size())
                {
                        int v = qu.front();
                        qu.pop();
                        for (int u : in[v])
                                if (!F[u])
                                {
                                        if (!A[u])
                                                F[u] = 1, qu.push(u);
                                        else
                                        {
                                                D[u] ++;
                                                if (D[u] == (int)out[u].size())
                                                        F[u] = 1, qu.push(u);
                                        }
                                }
                }
        }

        vector < int > Rs;
        for (int i = 0; i < n; i ++)
                Rs.push_back(F[i] == 0);
        return Rs;

}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51