Submission #306207

#	Time	Username	Problem	Language	Result	Execution time	Memory
306207		CaroLinda	Stray Cat (JOI20_stray)	C++14	100 / 100	69 ms	16976 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
 
#define debug //printf
#define pii pair<int,int>
#define ff first
#define ss second
#define mk make_pair
#define sz(x) (int)(x.size() )
#define ll long long
#define all(x) x.begin(),x.end()
 
const int MAXN = 2e4+10 ;
 
using namespace std ;
 
vector<pii> adj[MAXN] ;
int marcas[MAXN] , dist[MAXN] ;
int seq[6] = {0,1,0,0,1,1} ;
 
void dfs(int x, int father , int curIdx , int dist = 1 ) //curIdx eh o que eu tenho que colocar nas minhas proximas arestas
{
	
	if( sz(adj[x]) != 2 ) curIdx = !seq[curIdx] ;
	else curIdx = (curIdx == 5) ? 0 : (curIdx+1) ;

	for(auto e : adj[x] ) 
	{
		if(e.ff == father )  continue ;
 
		marcas[e.ss] = seq[curIdx] ;
 
      dfs(e.ff, x, curIdx , dist+1 ) ;
				 
	}
 
}
  
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) 
{
 
	for(int i = 0 ; i < M ; i++ )
	{
		adj[ U[i] ].push_back(mk(V[i] , i ) ) ;
		adj[ V[i] ].push_back( mk(U[i],i) )  ;
	}
 

	if(A >= 3 )
	{

		//Constroi a arvore da bfs

		for(int i = 1 ; i < N ; i++ ) dist[i] = -1 ;

		vector<int> fila ;

		int ini = 0 ;
		fila.push_back(0) ;

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

			for(auto e : adj[x] ) 
			{
				if(dist[e.ff] != -1 ) continue ;

				fila.push_back(e.ff) ;
				dist[e.ff] = dist[x] + 1 ;

			}

		}


  		for(int i = 0 ; i < M ; i++ )
  		{
  			int a = U[i] ;
  			int b = V[i] ;

  			if( dist[a] == dist[b] ) marcas[i] = dist[a] % 3 ;
  			else marcas[i] = min(dist[a] , dist[b] ) % 3 ;

  		}

	}
	else
	{
		for(auto neigh : adj[0] )
		{
			marcas[neigh.ss] = 0 ;
			dfs(neigh.ff, 0, 0 ) ;
		}
	}	
 
	for(int i = 0 ; i < M ; i++ ) debug("Pintei %d %d de %d\n", U[i] , V[i] , marcas[i] ) ;
 
   vector<int> answer(M,0) ;
   for(int i = 0 ; i < M; i++ ) answer[i] = marcas[i] ;
	
	return answer ;
}

Catherine

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

#define debug //printf
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define pii pair<int,int>

using namespace std ;

set< string > reversedOrder ;
bool is3 ;

void Init(int A, int B) 
{
	string seq = "010011" ;

	if(A >= 3 ) is3 = true ;

	//Creating reversedOrder
	for(int i = 0 ,ant = 5 ; i < 6 ; i++ , ant++ )
	{

		if(ant == 6 ) ant = 0 ;

		string str ;
		for(int j = i; j != ant ; j = (j == 5 ) ? 0 : (j+1) )
			str.push_back(seq[j] ) ;

		reversedOrder.insert(str) ;
	}
	                          
}

bool justGo , isFirst = true ;
int wentBefore ;
string str ;

int Move(vector<int> y) 
{
	if(is3)
	{
		int qtdNeigh = (y[0] > 0 ) + (y[1] > 0 ) + (y[2] > 0 ) ;

		if(qtdNeigh == 1 ) 
		{
			for(int i = 0 ; i < 3 ; i++ )
				if(y[i] > 0 ) return i ;
		}

		if(y[0] > 0 && y[1] > 0 ) return 0 ;
		if(y[1] > 0 && y[2] > 0 ) return 1 ;
		if(y[2] >0 && y[0] > 0 ) return 2 ;

	}

	
	debug("meu vetor ta %d %d e justGo eh %d\n", y[0] , y[1] , justGo) ;
	
	int qtdNeigh = y[0] + y[1] ;
	
	if(qtdNeigh == 0)
	{
		justGo = true ;
		return -1 ;
	}

	if(isFirst)
	{
		isFirst = false ;

		if(qtdNeigh == 1 )
		{
			
			wentBefore = (y[0] == 1 ) ? 0 : 1 ;
			justGo = true ;
			return wentBefore ;
		}
		if(qtdNeigh == 2 )
		{

			if( y[0] && y[1] )
			{
				str.push_back('0') ;
				str.push_back('1') ;
				wentBefore = 1 ;
				return 1 ;
			}
			int idx = (y[0] > y[1] ) ? 0 : 1 ;

			str.push_back('0' + idx ) ;
			str.push_back('0' + idx ) ;
			wentBefore = idx ;
			return idx ;

		}

	   wentBefore = (y[0] < y[1] ) ? 0 : 1 ;
	   justGo = true ;

		return wentBefore ;
	}

	if(justGo)
	{
		if( qtdNeigh == 1 )
		{

			wentBefore = (y[0] > y[1] ) ? 0 : 1 ;
			return wentBefore ;
		}

		wentBefore = !wentBefore ;
		return wentBefore ;
	}

	if(qtdNeigh > 1 )
	{
		justGo = true ;
		
		if(y[!wentBefore] != 1 ) return -1 ;

		wentBefore = !wentBefore;
		return wentBefore;

	}

	//Ainda estou presa na corrente
	str.push_back( '0' + ( (y[0] == 1) ? 0 : 1 ) ) ;

	if(sz(str) == 5 )
	{


		justGo = true ;

		if( reversedOrder.find(str) != reversedOrder.end() ) return -1 ;
		else 
		{
			wentBefore = (y[0] == 1 ) ? 0 : 1 ;
			return wentBefore ;
		}
	}

	wentBefore = (y[0] == 1 ) ? 0 : 1 ;

	return wentBefore ;

}

Compilation message (stderr)

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:97:38: warning: left operand of comma operator has no effect [-Wunused-value]
   97 |  for(int i = 0 ; i < M ; i++ ) debug("Pintei %d %d de %d\n", U[i] , V[i] , marcas[i] ) ;
      |                                      ^~~~~~~~~~~~~~~~~~~~~~

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:62:8: warning: left operand of comma operator has no effect [-Wunused-value]
   62 |  debug("meu vetor ta %d %d e justGo eh %d\n", y[0] , y[1] , justGo) ;
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9