Submission #136613

#	Time	Username	Problem	Language	Result	Execution time	Memory
136613		CaroLinda	Toy Train (IOI17_train)	C++14	0 / 100	2078 ms	1272 KiB

train

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 5010 ;
const int MAXM  = 20010 ;

using namespace std ;


int n ,  m ;

int a[MAXN] , r[MAXN] , v[MAXM] , u[MAXM] ;

int dp[MAXN][MAXN] ;

vector<int> adj[MAXN] ;

// -------------------

bool goodSelfLoop(int i)
{
	for(int j : adj[i])
		if( j == i && r[i] && ( a[i] || adj[i].size() == 1 ) )
			return true ;

	return false ;
}

bool badSelfLoop(int i)
{

	for(int j : adj[i])
		if( j == i && !r[i] && ( !a[i] || adj[i].size() == 1)  )
			return true ;

	return false ;

}

vector<int> parcial()
{

	vector<int> ans(n) ;


	for(int i = 0 ; i < n ; i++ )
	{

		int x = i ;
		bool isBad = false ;

		while(true)
		{

			if( badSelfLoop(x) )
				{ isBad = true ; break ; }

			else if ( goodSelfLoop(x) )
				{ isBad = false ; break ; }

			for(int j : adj[x])
				if( j != x )
					{ x = j ; break ; }

		}

		for(int j = i ; j <= x ; j++ )
			ans[i] = !isBad ;

		i = x ;


	}

	return ans ;

}


vector<int> who_wins(vector<int> A , vector<int> R, vector<int> U , vector<int> V )
{

	n = A.size() ;
	m = U.size() ;

	lp(i,0,n) a[i] = A[i] , r[i] = R[i] ;
	lp(i,0,m) adj[U[i]].pb(V[i]) ;

	return parcial() ;

}

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