Submission #230663

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
230663	2020-05-11T00:57:03 Z	AmineWeslati	Zoo (COCI19_zoo)	C++14	45 / 110	2000 ms	24076 KB

zoo

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
#define int ll
typedef double db;
typedef long double ld;

typedef pair<int,int> pi;
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;

#define pb push_back
#define eb emplace_back
#define pf push_front

#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int MOD = 1e9+7; //998244353
const ll INF = 1e18;
const int nx[4]={0,0,1,-1}, ny[4]={1,-1,0,0};

set <pi> s;
int R,C;
char g[1001][1001];
bool vis[1001][1001];
char c;

void dfs(int x, int y){
   s.insert({x,y});
   vis[x][y]=true;
   if(c=='T')g[x][y]='B';
   else g[x][y]='T';

   for(int m=0; m<4; m++){
      int nwx=x+nx[m],nwy=y+ny[m];
      if(nwx<0||nwy<0||nwx>=R||nwy>=C||vis[nwx][nwy]||g[nwx][nwy]!=c) continue;
      dfs(nwx,nwy);
   }
}

int32_t main(){
   boost;
	cin>>R>>C;
	 int nb=0;
	for(int i=0; i<R; i++) for(int j=0; j<C; j++){
      cin>>g[i][j];
      if(g[i][j]!='*') nb++;
	}

	int ans=0;
	while(sz(s)<nb){
      memset(vis,false,sizeof(vis));
      c=g[R-1][C-1];
      dfs(R-1,C-1);
      ans++;
	}
	cout << ans << endl;

   return 0;
}

Subtask #1

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1280 KB	Output is correct
2	Correct	5 ms	1408 KB	Output is correct
3	Correct	5 ms	1408 KB	Output is correct
4	Correct	6 ms	1536 KB	Output is correct
5	Correct	7 ms	1792 KB	Output is correct
6	Correct	8 ms	1920 KB	Output is correct
7	Correct	9 ms	1792 KB	Output is correct
8	Correct	23 ms	1792 KB	Output is correct
9	Correct	23 ms	1792 KB	Output is correct
10	Correct	29 ms	1920 KB	Output is correct
11	Correct	28 ms	1792 KB	Output is correct
12	Correct	33 ms	1920 KB	Output is correct
13	Correct	24 ms	1792 KB	Output is correct
14	Correct	23 ms	1792 KB	Output is correct
15	Correct	25 ms	1792 KB	Output is correct

Subtask #2

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1280 KB	Output is correct
2	Correct	5 ms	1408 KB	Output is correct
3	Correct	5 ms	1408 KB	Output is correct
4	Correct	6 ms	1536 KB	Output is correct
5	Correct	7 ms	1792 KB	Output is correct
6	Correct	8 ms	1920 KB	Output is correct
7	Correct	9 ms	1792 KB	Output is correct
8	Correct	23 ms	1792 KB	Output is correct
9	Correct	23 ms	1792 KB	Output is correct
10	Correct	29 ms	1920 KB	Output is correct
11	Correct	28 ms	1792 KB	Output is correct
12	Correct	33 ms	1920 KB	Output is correct
13	Correct	24 ms	1792 KB	Output is correct
14	Correct	23 ms	1792 KB	Output is correct
15	Correct	25 ms	1792 KB	Output is correct
16	Correct	79 ms	9848 KB	Output is correct
17	Correct	85 ms	10744 KB	Output is correct
18	Correct	77 ms	9596 KB	Output is correct
19	Correct	121 ms	12664 KB	Output is correct
20	Correct	78 ms	9976 KB	Output is correct
21	Execution timed out	2078 ms	24076 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-