oj.uz

Submission #401319

# Submission time Handle Problem Language Result Execution time Memory
401319 2021-05-09T20:41:02 Z hgmhc 토마토 (KOI13_tomato) C++17
16 / 16
 126 ms 11456 KB 
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
using pi = pair<int,int>;
#define F first
#define S second
#define isInBoard(r,c) (r >= 0 && r < n && c >= 0 && c < m)
   
const int maxn = 1000, maxm = 1000;
int n, m, ans, tm[maxn][maxm], days[maxn][maxm];
bool visited[maxn][maxm], isThereNotRiped;
queue<pi> q;
 
void bfs(pi s, pi e) {
    if (isInBoard(e.F, e.S) && !visited[e.F][e.S] && !tm[e.F][e.S]) {
        visited[e.F][e.S] = true;
        days[e.F][e.S] = days[s.F][s.S]+1;
        q.push({e.F, e.S});
        ans = max(ans, days[e.F][e.S]);
    }
    return;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            cin >> tm[r][c];
            if (!tm[r][c]) isThereNotRiped = true;
            else if (tm[r][c] == 1) {
                q.push({r, c});
                days[r][c] = 0; visited[r][c] = true;
            }
        }
    }
    if (!isThereNotRiped) {
        cout << 0;
        return 0;
    }
    while (!q.empty()) {
        pi s = q.front(); q.pop();
        tm[s.F][s.S] = 1;
        bfs(s, {s.F, s.S+1});
        bfs(s, {s.F+1, s.S});
        bfs(s, {s.F, s.S-1});
        bfs(s, {s.F-1, s.S});
    }
    for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) {
        if (!tm[r][c]) {
            cout << -1;
            return 0;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #2
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #3
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 720 KB Output is correct

Subtask #4
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2124 KB Output is correct
2 Correct 6 ms 2200 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 716 KB Output is correct

Subtask #5
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1140 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 6 ms 4556 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct

Subtask #6
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 6 ms 2064 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 6 ms 2124 KB Output is correct

Subtask #7
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5988 KB Output is correct
2 Correct 25 ms 9548 KB Output is correct
3 Correct 13 ms 3404 KB Output is correct
4 Correct 12 ms 3276 KB Output is correct

Subtask #8
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8124 KB Output is correct
2 Correct 42 ms 7236 KB Output is correct
3 Correct 7 ms 1740 KB Output is correct
4 Correct 11 ms 1120 KB Output is correct

Subtask #9
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4636 KB Output is correct
2 Correct 103 ms 10416 KB Output is correct
3 Correct 12 ms 1612 KB Output is correct
4 Correct 55 ms 8656 KB Output is correct

Subtask #10
1.6 / 1.6

# Verdict Execution time Memory Grader output
1 Correct 121 ms 11192 KB Output is correct
2 Correct 126 ms 11336 KB Output is correct
3 Correct 98 ms 11456 KB Output is correct
4 Correct 78 ms 9292 KB Output is correct