Submission #498408

#	Time	Username	Problem	Language	Result	Execution time	Memory
498408		vinnipuh01	Robots (APIO13_robots)	C++17	30 / 100	46 ms	16744 KiB

robots

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

char c[ 501 ][ 501 ];
int k, n, m, d[ 10 ][ 250001 ], pr[ 10 ], p[ 10 ], r[ 10 ];
set <pair<int, int> > st;
vector <int> v[ 250001 ];
vector <pair<int, pair<int, int> > > vv;

void f( int i, int j ) {
	if ( !i || !j || i > n || j > m || c[ i ][ j ] == 'x' )
		return;
	pos = ( i - 1 ) * m + j;
	if ( ans == 1 ) {
		if ( c[ i ][ j ] == 'x' )
			return;
		else if ( c[ i ][ j ] == 'A' ) {
			j --;
			ans = 4;
		}
		else if ( c[ i ][ j ] == 'C' ) {
			j ++;
			ans = 2;
		}
		else
			i --;
		return f( i, j );
	}
	else if ( ans == 2 ) {
		if ( c[ i ][ j ] == 'A' ) {
			i --;
			ans = 1;
		}
		else if ( c[ i ][ j ] == 'C' ) {
			i ++;
			ans = 3;
		}
		else if ( c[ i ][ j ] == 'x' )
			return;
		else
			j ++;
		return f( i, j );
	}
	else if ( ans == 3 ) {
		if ( c[ i ][ j ] == 'x' ) 
			return;
		if ( c[ i ][ j ] == 'A' )
			ans = 2, j ++;
		else if ( c[ i ][ j ] == 'C' )
			ans = 4, j --;
		else
			i ++;
		return f( i, j );
	}
	else {
		if ( c[ i ][ j ] == 'x' )
			return;
		if ( c[ i ][ j ] == 'A' )
			ans = 3, i ++;
		else if ( c[ i ][ j ] == 'C' )
			ans = 1, i --;
		else
			j --;
		return f( i, j );
	}
}

int fin( int a ) {
	if ( pr[ a ] == a )
		return a;
	return pr[ a ] = fin( pr[ a ] );
}

void unin( int a, int b ) {
	a = fin( a );
	b = fin( b );
	if ( a == b )
		return;
	if ( r[ a ] < r[ b ] )
		swap( a, b );
	r[ a ] += r[ b ];
	pr[ b ] = a;
}

main () {
	cin >> k >> m >> n;
	for ( int i = 1; i <= k; i ++ )
		pr[ i ] = i, r[ i ] = 1;
	for ( int i = 1; i <= n; i ++ ) {
		for ( int j = 1; j <= m; j ++ ) {
			cin >> c[ i ][ j ];
			num = ( i - 1 ) * m + j;
			if ( c[ i ][ j ] >= '1' && c[ i ][ j ] <= '9' )
				p[ c[ i ][ j ] - '0' ] = num;
		}
	}
	for ( int i = 1; i <= n; i ++ ) {
		for ( int j = 1; j <= m; j ++ ) {
			num = ( i - 1 ) * m + j;
			pos = num;
			ans = 1;
			f( i - 1, j );
			v[ num ].push_back( pos );
			pos = num;
			ans = 2;
			f( i, j + 1 );
			v[ num ].push_back( pos );
			pos = num;
			ans = 3;
			f( i + 1, j );
			v[ num ].push_back( pos );
			pos = num;
			ans = 4;
			f( i, j - 1 );
			v[ num ].push_back( pos ); 
		}
	}
	for ( int i = 1; i <= k; i ++ ) {
		for ( int j = 1; j <= n * m; j ++ )
			d[ i ][ j ] = oo;
		d[ i ][ p[ i ] ] = 0;
		st.insert( { d[ i ][ p[ i ] ], p[ i ] } );
		while ( st.size() ) {
			num = st.begin()->second;
			st.erase( st.begin() );
			for ( auto to : v[ num ] ) {
				if ( d[ i ][ to ] > d[ i ][ num ] + 1 ) {
					st.erase( { d[ i ][ to ], to } );
					d[ i ][ to ] = d[ i ][ num ] + 1;
					st.insert( { d[ i ][ to ], to } );
				}
			}
		}
	}
//	for ( int i = 1; i <= k; i ++ ) {
//		for ( int j = 1; j <= k; j ++ ) {
//			vv.push_back( { d[ i ][ p[ j ] ], make_pair( i, j ) } );
//		}
//	}
//	sort( vv.begin(), vv.end() );
//	ans = 0;
//	for ( auto i : vv ) {
//		if ( fin( i.second.first ) != fin( i.second.second ) ) {
//			cout << i.second.first << " " << i.second.second << "\n";
//			ans += i.first;
//			unin( i.second.second, i.second.first );
//		}
//	}
	ans = oo;
	for ( int i = 1; i <= n * m; i ++ ) {
		ans = min( ans, d[ 1 ][ i ] + d[ 2 ][ i ] );
	}
	if ( ans == oo )
		cout << "-1";
	else
		cout << ans;
}

Compilation message (stderr)

robots.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main () {
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40