| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1057686 |
2024-08-14T03:19:08 Z |
Requiem |
Zoo (COCI19_zoo) |
C++17 |
|
209 ms |
57944 KB |
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "zoo"
using namespace std;
/**Debugging Tool **/
void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*----------------------------------*/
/** Vector nhieu chieu **/
template<int D, typename T>
struct Vec: public vector<Vec<D - 1, T>>{
static_assert(D >= 1, "vector dimensions must be greater than 0");
template<typename... Args>
Vec(int n = 0, Args... args): vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)){
}
};
template<typename T>
struct Vec<1, T>: public vector<T> {
Vec(int n = 0, const T& val = T()): vector<T>(n, val) {};
};
/*--------------------------------*/
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 1009 + 9;
int n, m;
char str[MAXN][MAXN];
int idComponent[MAXN][MAXN], componentCount = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<ii> q;
vector<vector<int>> g;
map<ii, bool> mp;
bool valid(int x, int y){
return x >= 1 and x <= n and y >= 1 and y <= m and str[x][y] != '*';
}
void bfs(int x, int y){
idComponent[x][y] = ++componentCount;
q.push(ii(x, y));
while(!q.empty()){
int x1 = q.front().fi;
int y1 = q.front().se;
q.pop();
for(int d = 0; d < 4; d++){
int nx = x1 + dx[d];
int ny = y1 + dy[d];
if (!idComponent[nx][ny] and valid(nx, ny) and str[nx][ny] == str[x1][y1]){
idComponent[nx][ny] = componentCount;
q.push(ii(nx, ny));
}
}
}
}
ii best = ii(0, 0);
int dist[MAXN * MAXN];
void dfs(int u, int p, int d){
queue<int> q;
q.push(1);
memset(dist, 0x3f, sizeof(dist));
dist[1] = 1;
int ans = 0;
while(!q.empty()){
int u = q.front();
maximize(ans, dist[u]);
q.pop();
for(auto v: g[u]){
if (minimize(dist[v], dist[u] + 1)){
q.push(v);
}
}
}
cout << ans << endl;
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> str[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if (idComponent[i][j] == 0 and str[i][j] != '*'){
bfs(i, j);
}
}
}
g.resize(componentCount + 1);
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// printf("%lld ", idComponent[i][j]);
// }
// printf("\n");
// }
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if (i < n and str[i][j] != '*' and str[i + 1][j] != '*' and str[i + 1][j] != str[i][j]) {
// printf("%lld %lld %lld\n", i, j, idComponent[i][j]);
if (mp.find(ii(idComponent[i][j], idComponent[i + 1][j])) == mp.end()){
g[idComponent[i][j]].pb(idComponent[i + 1][j]);
g[idComponent[i + 1][j]].pb(idComponent[i][j]);
// printf("%lld %lld %lld %lld\n", i, j, i + 1, j);
// printf("%lld %lld\n", idComponent[i][j], idComponent[i + 1][j]);
mp[ii(idComponent[i][j], idComponent[i + 1][j])] = true;
mp[ii(idComponent[i + 1][j], idComponent[i][j])] = true;
}
}
if (j < m and str[i][j] != '*' and str[i][j + 1] != '*' and str[i][j] != str[i][j + 1]) {
if (mp.find(ii(idComponent[i][j], idComponent[i][j + 1])) == mp.end()){
// printf("%lld %lld %lld %lld\n", i, j, i, j + 1);
g[idComponent[i][j]].pb(idComponent[i][j + 1]);
g[idComponent[i][j + 1]].pb(idComponent[i][j]);
mp[ii(idComponent[i][j], idComponent[i][j + 1])] = true;
// printf("%lld %lld\n",idComponent[i][j], idComponent[i][j + 1]);
mp[ii(idComponent[i][j + 1], idComponent[i][j])] = true;
}
}
}
}
////
dfs(idComponent[n][m], -1, 0);
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
Compilation message
zoo.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
129 | main()
| ^~~~
zoo.cpp: In function 'int main()':
zoo.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zoo.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6608 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 8 |
Correct |
2 ms |
7136 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 10 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 11 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 12 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 13 |
Correct |
2 ms |
7248 KB |
Output is correct |
| 14 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 15 |
Correct |
2 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6608 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 7 |
Correct |
1 ms |
7004 KB |
Output is correct |
| 8 |
Correct |
2 ms |
7136 KB |
Output is correct |
| 9 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 10 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 11 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 12 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 13 |
Correct |
2 ms |
7248 KB |
Output is correct |
| 14 |
Correct |
2 ms |
7260 KB |
Output is correct |
| 15 |
Correct |
2 ms |
7004 KB |
Output is correct |
| 16 |
Correct |
13 ms |
10580 KB |
Output is correct |
| 17 |
Correct |
16 ms |
10824 KB |
Output is correct |
| 18 |
Correct |
19 ms |
10836 KB |
Output is correct |
| 19 |
Correct |
15 ms |
10820 KB |
Output is correct |
| 20 |
Correct |
15 ms |
10740 KB |
Output is correct |
| 21 |
Correct |
200 ms |
55636 KB |
Output is correct |
| 22 |
Correct |
209 ms |
55260 KB |
Output is correct |
| 23 |
Correct |
193 ms |
55648 KB |
Output is correct |
| 24 |
Correct |
183 ms |
57944 KB |
Output is correct |
| 25 |
Correct |
182 ms |
56660 KB |
Output is correct |
| 26 |
Correct |
179 ms |
56396 KB |
Output is correct |
| 27 |
Correct |
209 ms |
55124 KB |
Output is correct |
| 28 |
Correct |
191 ms |
55128 KB |
Output is correct |
| 29 |
Correct |
185 ms |
57428 KB |
Output is correct |
| 30 |
Correct |
184 ms |
56884 KB |
Output is correct |
