Submission #568180

#	Time	Username	Problem	Language	Result	Execution time	Memory
568180		MohamedAhmed04	Travelling Salesperson (CCO20_day2problem1)	C++14	25 / 25	535 ms	35988 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2004 ;

int arr[MAX][MAX] ;
int n ;

int prv[MAX] , nxt[MAX] ;

void solve(int st)
{
	for(int i = 1 ; i <= n ; ++i)
		nxt[i] = prv[i] = -1 ;
	int x = -1 , last = st , stcol = -1 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(i == st)
			continue ;
		if(stcol == -1)
			nxt[st] = i , prv[i] = st , stcol = arr[st][i] , last = i ;
		else if(x == -1)
		{
			nxt[last] = i , prv[i] = last ;
			if(arr[last][i] != stcol)
				x = last ;
			last = i ;
		}
		else
		{
			int a = prv[x] ;
			if(arr[x][i] == stcol)
			{
				int y = nxt[x] ;
				nxt[x] = i , prv[i] = x ;
				nxt[i] = y , prv[y] = i ;
			}
			else
			{
				nxt[a] = i , prv[i] = a ;
				nxt[i] = x , prv[x] = i ;
				if(a == st)
					stcol = arr[a][i] ;
			}
			int cur = a ;
			x = -1 ;
			for(int k = 0 ; k < 10 ; ++k)
			{
				if(prv[cur] == -1)
				{
					cur = nxt[cur] ;
					continue ;
				}
				if(nxt[cur] == -1)
					break ;
				if(arr[prv[cur]][cur] != arr[cur][nxt[cur]])
				{
					x = cur ;
					break ;
				}
				cur = nxt[cur] ;
			}
		}
	}
	cout<<n<<"\n" ;
	int now = st ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cout<<now<<" " ;
		now = nxt[now] ;
	}
	cout<<"\n" ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j < i ; ++j)
		{
			char c ; 
			cin>>c ;
			if(c == 'B')
				arr[i][j] = arr[j][i] = 0 ;
			else
				arr[i][j] = arr[j][i] = 1 ;
		}
	}
	for(int i = 1 ; i <= n ; ++i)
		solve(i) ;
	return 0 ;
}		

• Subtask 1: 25 / 25