Submission #290884

#	Time	Username	Problem	Language	Result	Execution time	Memory
290884		Kastanda	Toy Train (IOI17_train)	C++11	0 / 100	1937 ms	75192 KiB

train

// M
#include<bits/stdc++.h>
#include "train.h"
using namespace std;
const int N = 5005;
int n, m, A[N], R[N];
vector < int > Adj[N];
bool dp[N * 3][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 ++)
        {
                Adj[_U[i]].push_back(_V[i]);
                Adj[_V[i]].push_back(_U[i]);
        }

        for (int i = 0; i < n; i ++)
                if (R[i]) dp[0][i] = 1;

        for (int k = 1; k <= n * 3; k ++)
        {
                for (int v = 0; v < n; v ++)
                {
                        if (A[v] == 1)
                        {
                                for (int u : Adj[v])
                                        dp[k][v] |= (dp[k - 1][u] | R[u]);
                        }
                        else
                        {
                                dp[k][v] = 1;
                                for (int u : Adj[v])
                                        dp[k][v] &= (dp[k - 1][u] | R[u]);
                        }
                }
        }
        vector < int > Rs;
        for (int i = 0; i < n; i ++)
        {
                int w = 0;
                for (int k = n * 2; k <= n * 3; k ++)
                        if (dp[k][i])
                                w = 1;
                Rs.push_back(w);
        }
        return Rs;
}

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