Submission #420214
Source Code Expand
#include <iostream> #include <iomanip> #include <sstream> #include <vector> #include <string> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <functional> #include <iterator> #include <limits> #include <numeric> #include <utility> #include <cmath> #include <cassert> #include <cstdio> using namespace std; using namespace placeholders; using LL = long long; using ULL = unsigned long long; using VI = vector< int >; using VVI = vector< vector< int > >; using VS = vector< string >; using SS = stringstream; using PII = pair< int, int >; using VPII = vector< pair< int, int > >; template < typename T = int > using VT = vector< T >; template < typename T = int > using VVT = vector< vector< T > >; template < typename T = int > using LIM = numeric_limits< T >; template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; } template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; } template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }; template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) ( c ).begin(), ( c ).end() #define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t ) #define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + ( p ), ( c ).end() #define SZ( v ) ( (int)( v ).size() ) #define PB push_back #define EM emplace #define EB emplace_back #define BI back_inserter #define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() ) #define MP make_pair #define fst first #define snd second #define DUMP( x ) cerr << #x << " = " << ( x ) << endl constexpr char *MSG[] = { "No", "Yes" }; class UnionFind { private: const int N; vector<int> parent; vector<int> rank; int groups_; std::vector< int > sizes; public: UnionFind( int n ) : N( n ), parent( N ), rank( N, 0 ), groups_( N ), sizes( N, 1 ) { std::iota( parent.begin(), parent.end(), 0 ); return; } int find( int x ) { if ( parent[x] == x ) { return x; } return parent[x] = find( parent[x] ); } bool same( int x, int y ) { return find( x ) == find( y ); } bool unite( int x, int y ) { x = find( x ); y = find( y ); if ( x == y ) { return false; } if ( rank[x] < rank[y] ) { parent[x] = y; sizes[y] += sizes[x]; } else { parent[y] = x; sizes[x] += sizes[y]; if ( rank[x] == rank[y] ) { ++rank[x]; } } --groups_; return true; } int groups() const { return groups_; } int groupSize( const int x ) { return sizes[ find( x ) ]; } }; // UnionFind( N ) // find( x ) // same( x, y ) // unite( x, y ) // groups() // groupSize( x ) int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int H, W; cin >> H >> W; VS board( H ); cin >> board; UnionFind uf( H * W ); PII s, g; REP( i, H ) { REP( j, W ) { if ( board[i][j] == 's' ) { s = MP( i, j ); } if ( board[i][j] == 'g' ) { g = MP( i, j ); } if ( i + 1 < H && board[i][j] != '#' && board[ i + 1 ][j] != '#' ) { uf.unite( i * W + j, ( i + 1 ) * W + j ); } if ( j + 1 < W && board[i][j] != '#' && board[i][ j + 1 ] != '#' ) { uf.unite( i * W + j, i * W + j + 1 ); } } } cout << MSG[ uf.same( s.fst * W + s.snd, g.fst * W + g.snd ) ] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - 深さ優先探索 |
User | torus711 |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 4037 Byte |
Status | AC |
Exec Time | 50 ms |
Memory | 4140 KB |
Compile Error
./Main.cpp:65:39: warning: deprecated conversion from string constant to ‘char*’ [-Wwrite-strings] constexpr char *MSG[] = { "No", "Yes" }; ^ ./Main.cpp:65:39: warning: deprecated conversion from string constant to ‘char*’ [-Wwrite-strings]
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt |
All | 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_min_01.txt | AC | 27 ms | 924 KB |
00_min_02.txt | AC | 27 ms | 800 KB |
00_min_03.txt | AC | 25 ms | 920 KB |
00_min_04.txt | AC | 24 ms | 932 KB |
00_min_05.txt | AC | 25 ms | 924 KB |
00_min_06.txt | AC | 24 ms | 800 KB |
00_min_07.txt | AC | 24 ms | 800 KB |
00_min_08.txt | AC | 25 ms | 800 KB |
00_sample_01.txt | AC | 24 ms | 796 KB |
00_sample_02.txt | AC | 25 ms | 760 KB |
00_sample_03.txt | AC | 25 ms | 800 KB |
00_sample_04.txt | AC | 25 ms | 792 KB |
00_sample_05.txt | AC | 25 ms | 788 KB |
01_rnd_00.txt | AC | 35 ms | 3996 KB |
01_rnd_01.txt | AC | 39 ms | 4000 KB |
01_rnd_02.txt | AC | 43 ms | 3996 KB |
01_rnd_03.txt | AC | 38 ms | 4004 KB |
01_rnd_04.txt | AC | 39 ms | 4004 KB |
01_rnd_05.txt | AC | 42 ms | 3996 KB |
01_rnd_06.txt | AC | 43 ms | 4000 KB |
01_rnd_07.txt | AC | 42 ms | 4000 KB |
01_rnd_08.txt | AC | 34 ms | 4004 KB |
01_rnd_09.txt | AC | 36 ms | 4128 KB |
01_rnd_10.txt | AC | 39 ms | 4000 KB |
01_rnd_11.txt | AC | 35 ms | 4008 KB |
01_rnd_12.txt | AC | 38 ms | 4124 KB |
01_rnd_13.txt | AC | 39 ms | 4012 KB |
01_rnd_14.txt | AC | 39 ms | 4124 KB |
01_rnd_15.txt | AC | 43 ms | 4140 KB |
01_rnd_16.txt | AC | 34 ms | 4004 KB |
01_rnd_17.txt | AC | 40 ms | 4128 KB |
01_rnd_18.txt | AC | 33 ms | 4124 KB |
01_rnd_19.txt | AC | 38 ms | 4008 KB |
02_rndhard_00.txt | AC | 38 ms | 4120 KB |
02_rndhard_01.txt | AC | 40 ms | 4000 KB |
02_rndhard_02.txt | AC | 40 ms | 4000 KB |
02_rndhard_03.txt | AC | 40 ms | 4000 KB |
02_rndhard_04.txt | AC | 40 ms | 4132 KB |
02_rndhard_05.txt | AC | 42 ms | 3948 KB |
02_rndhard_06.txt | AC | 40 ms | 4004 KB |
02_rndhard_07.txt | AC | 40 ms | 4004 KB |
02_rndhard_08.txt | AC | 41 ms | 4008 KB |
02_rndhard_09.txt | AC | 38 ms | 4000 KB |
02_rndhard_10.txt | AC | 40 ms | 4004 KB |
02_rndhard_11.txt | AC | 39 ms | 4004 KB |
02_rndhard_12.txt | AC | 41 ms | 3996 KB |
02_rndhard_13.txt | AC | 40 ms | 4004 KB |
02_rndhard_14.txt | AC | 39 ms | 4000 KB |
02_rndhard_15.txt | AC | 40 ms | 3992 KB |
02_rndhard_16.txt | AC | 40 ms | 4012 KB |
02_rndhard_17.txt | AC | 40 ms | 4000 KB |
02_rndhard_18.txt | AC | 40 ms | 4016 KB |
02_rndhard_19.txt | AC | 40 ms | 4012 KB |
02_rndhard_20.txt | AC | 40 ms | 4004 KB |
02_rndhard_21.txt | AC | 40 ms | 4000 KB |
02_rndhard_22.txt | AC | 42 ms | 4004 KB |
02_rndhard_23.txt | AC | 40 ms | 3932 KB |
02_rndhard_24.txt | AC | 42 ms | 4004 KB |
02_rndhard_25.txt | AC | 40 ms | 4128 KB |
02_rndhard_26.txt | AC | 40 ms | 3996 KB |
02_rndhard_27.txt | AC | 40 ms | 4000 KB |
02_rndhard_28.txt | AC | 41 ms | 4008 KB |
02_rndhard_29.txt | AC | 40 ms | 3996 KB |
02_rndhard_30.txt | AC | 39 ms | 4000 KB |
02_rndhard_31.txt | AC | 39 ms | 4004 KB |
02_rndhard_32.txt | AC | 39 ms | 3996 KB |
02_rndhard_33.txt | AC | 40 ms | 4004 KB |
02_rndhard_34.txt | AC | 40 ms | 4008 KB |
02_rndhard_35.txt | AC | 50 ms | 3936 KB |
02_rndhard_36.txt | AC | 42 ms | 4000 KB |
02_rndhard_37.txt | AC | 43 ms | 4000 KB |
02_rndhard_38.txt | AC | 41 ms | 4008 KB |
02_rndhard_39.txt | AC | 42 ms | 3944 KB |
03_rndhardsmall_00.txt | AC | 25 ms | 788 KB |
03_rndhardsmall_01.txt | AC | 25 ms | 732 KB |
03_rndhardsmall_02.txt | AC | 27 ms | 924 KB |
03_rndhardsmall_03.txt | AC | 24 ms | 928 KB |
03_rndhardsmall_04.txt | AC | 26 ms | 796 KB |
03_rndhardsmall_05.txt | AC | 25 ms | 920 KB |
03_rndhardsmall_06.txt | AC | 25 ms | 920 KB |
03_rndhardsmall_07.txt | AC | 27 ms | 932 KB |
03_rndhardsmall_08.txt | AC | 25 ms | 928 KB |
03_rndhardsmall_09.txt | AC | 23 ms | 808 KB |