Submission #290913

#	Time	Username	Problem	Language	Result	Execution time	Memory
290913		Kastanda	Toy Train (IOI17_train)	C++11	11 / 100	11 ms	1792 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]);
        }


        queue < int > qu;
        for (int i = 0; i < n; i ++)
                if (R[i])
                        Z[i] = 1, qu.push(i);
        while (qu.size())
        {
                int v = qu.front();
                qu.pop();
                for (int u : in[v])
                        if (!Z[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));
        for (int i = 0; i < n; i ++)
                if (!Z[i])
                        F[i] = 1, 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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51