Submission #404185

#	Time	Username	Problem	Language	Result	Execution time	Memory
404185		CaroLinda	Toy Train (IOI17_train)	C++14	100 / 100	1525 ms	2124 KiB

train

#include "train.h"
#include <bits/stdc++.h>

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

const int MAXN = 5010 ;

using namespace std; 

int N , M ;
bool is_a[MAXN] , is_charger[MAXN] ;
vector<int> good_for_a , good_for_b ;
bool marc[MAXN] ;
vector<int> adj[MAXN] , revAdj[MAXN] ;
vector<int> List ;
vector< vector<int> > components ;
int deg[MAXN] ;

void dfs1(int x)
{
	marc[x] = true ;

	for(auto e : adj[x] )
		if(!marc[e] ) dfs1(e) ;

	List.push_back(x) ;
}

void dfs2(int x)
{
	marc[x] = true ;
	components.back().pb(x) ;

	for(auto e : revAdj[x])
		if(!marc[e]) dfs2(e) ;
}

void goUpwards(vector<int> v)
{

	int ini = 0 ;

	while(ini < sz(v) )
	{
		int x = v[ini++] ;

		for(auto e : revAdj[x])
		{
			bool k = good_for_a[e]|good_for_b[e] ;

			if(!k && is_a[e] == good_for_a[x] )
			{
				if(is_a[e]) good_for_a[e] = true ;
				else good_for_b[e] = true ;

				v.pb(e) ;
			}
			else if(!k && sz(adj[e]) == 1 )
			{
				if(is_a[e]) good_for_b[e] = true ;
				else good_for_a[e] = true ;

				v.pb(e) ;
			}

			for(int i = 0 ; i < sz(adj[e]) ; i++ )
			{
				if( adj[e][i] != x ) continue ;
				swap(adj[e][i] , adj[e].back() ) ;
				adj[e].pop_back() ;
				break ;
			}
		}

		revAdj[x].clear() ;

		for(auto e : adj[x] )
			for(int i= 0 ; i < sz(revAdj[e]) ; i++ )
			{
				if( revAdj[e][i] != x ) continue ;
				swap(revAdj[e][i] , revAdj[e].back() ) ;
				revAdj[e].pop_back() ;
				break ;
			}

		adj[x].clear() ;
	}

//	for(auto e : v ) cout << e <<" " << good_for_a[e] << endl ;
}

bool solve()
{

	components.clear() ;
	List.clear() ;

	for(int i = 0 ; i < N ; i++ ) marc[i] = good_for_a[i]|good_for_b[i] ;

	for(int i = 0 ; i < N ; i++ )
	{
		if(marc[i]) continue ;

		deg[i] = 0 ;

		for(int j : adj[i] ) 
			if( !marc[j] ) deg[i]++ ;

		if(is_a[i]) deg[i] = 1 ;
	}

	for(int i = 0 ; i < N ; i++ )
		if(!marc[i]) dfs1(i) ;

	if( List.empty() ) return false ;

	for(int i : List ) marc[i] = false ;
	for(int i = sz(List)-1 ; i >= 0 ; i-- )
	{
		if(marc[List[i]]) continue ;

		components.push_back(vector<int>()) ;
		dfs2(List[i]) ;
	}

	for(int i : List ) marc[i] = false ;
	for(int i = 0 ; i < sz(components)-1 ; i++ )
		for(auto e : components[i] ) marc[e] = true ;

	for(auto e : components.back() )
	{
		if( !is_charger[e] ) continue ;

		vector<int> fila = {e} ;
		marc[e] = true ;
		int ini = 0 ;

		while( ini < sz(fila) )	
		{
			int x = fila[ini++] ;

			for(auto e : revAdj[x] )
			{
				if( marc[e] || is_charger[e] ) continue ;
				if( (--deg[e]) ) continue ;
				fila.pb( e ) ;
				marc[e] = true ;				
			}
		}	

	}

	vector<int> aux ;

	for(int i = 0 ; i < N ; i++ )
		if( !marc[i] ) aux.pb(i) ;

	if(aux.empty())
	{
		for(auto e : components.back()) good_for_a[e] = true ;
		goUpwards(components.back()) ;
		return true ;
	}

	//for(auto e : aux ) cout << e <<" " ;
	//cout << endl ;

	List.clear() ;
	components.clear() ;

	for(auto e : aux )
		if(!marc[e]) dfs1(e) ;

	for(int i : aux ) marc[i] = false ;
	for(int i = sz(List)-1 ; i >= 0 ; i-- )
	{
		if( marc[ List[i] ] ) continue ;

		components.pb(vector<int>()) ;
		dfs2(List[i]) ;
	}

	for(auto e : aux ) marc[e] = false ;
	for(int i = 0 ; i < sz(components) ; i++ )
	{
		bool cool = false ;

		for(auto e : components[i] ) marc[e] = true ;

		for(auto e : components[i] )
			for( auto ee : adj[e] )
				cool |= !marc[ee] ;

		for(auto e : components[i] ) marc[e] = true ;			

		if(cool) continue ;

		if( sz(components[i]) == 1 )
		{
			for(auto e : adj[components[i][0]]) cool |= (e == components[i][0] ) ;
			cool = !cool ;
		}

		if(cool) continue ;


		//I'm a leaf and a cycle
		for(auto e : components[i]) good_for_b[e] = true ;
		goUpwards(components[i]) ;
		return true ;
	}	

	return true ;
}

vector<int> who_wins( vector<int> a, vector<int> r, vector<int> u, vector<int> v) 
{
	N = sz(a) ;
	M = sz(u) ;

	good_for_a.resize( N , 0 ) ;
	good_for_b.resize( N , 0 ) ;

	lp(i,0,N) is_a[i] = a[i] ;
	lp(i,0,N) is_charger[i] = r[i] ;	
	lp(i,0,M)
	{
		adj[ u[i] ].pb( v[i] ) ;
		revAdj[ v[i] ].pb(u[i]) ;
	}

	while(solve()) {}

	return good_for_a ;
}

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