oj.uz

Submission #813922

# Submission time Handle Problem Language Result Execution time Memory
813922 2023-08-08T04:36:56 Z christinelynn Tracks in the Snow (BOI13_tracks) C++17
45.3125 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

char grid[4005][4005], cur;
bool vis[4005][4005];
int h, w, n, cnt, ans = 0;

bool valid(int i, int j){
    return (i>=1 && i<=h && j>=1 && j<=w);
}

void dfs(int i, int j){
    cnt++;
    vis[i][j] = 1;
    if(!vis[i+1][j] && valid(i+1,j) && grid[i+1][j]==cur){
        grid[i+1][j] = (cur=='F' ? 'R' : 'F');
        dfs(i+1,j);
    }
    if(!vis[i][j+1] && valid(i,j+1) && grid[i][j+1]==cur){
        grid[i][j+1] = (cur=='F' ? 'R' : 'F');
        dfs(i,j+1);
    }
    if(!vis[i-1][j] && valid(i-1,j) && grid[i-1][j]==cur){
        grid[i-1][j] = (cur=='F' ? 'R' : 'F');
        dfs(i-1,j);
    }
    if(!vis[i][j-1] && valid(i,j-1) && grid[i][j-1]==cur){
        grid[i][j-1] = (cur=='F' ? 'R' : 'F');
        dfs(i,j-1);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>h>>w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>grid[i][j];
            if(grid[i][j] != '.') n++;
        }
    }
    if(grid[1][1] == '.') {
        cout<<"0\n";
        return 0;
    }


    while(cnt<n){
        cnt = 0;
        cur = grid[1][1];
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++) vis[i][j] = 0;
        }

        grid[1][1] = (cur=='F' ? 'R' : 'F');
        dfs(1,1);
        ++ans;
    }

    cout<<ans<<'\n';

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 27004 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 27 ms 21092 KB Output is correct
5 Correct 30 ms 3664 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 26 ms 2576 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9920 KB Output is correct
13 Correct 32 ms 3664 KB Output is correct
14 Correct 31 ms 3628 KB Output is correct
15 Correct 216 ms 8784 KB Output is correct
16 Correct 188 ms 27068 KB Output is correct
17 Correct 231 ms 10268 KB Output is correct
18 Correct 36 ms 21068 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1227 ms 31464 KB Output is correct
2 Execution timed out 2065 ms 15996 KB Time limit exceeded
3 Execution timed out 2029 ms 48160 KB Time limit exceeded
4 Execution timed out 2059 ms 39572 KB Time limit exceeded
5 Execution timed out 2023 ms 33416 KB Time limit exceeded
6 Runtime error 1030 ms 1048576 KB Execution killed with signal 9
7 Correct 1143 ms 32364 KB Output is correct
8 Correct 1316 ms 31684 KB Output is correct
9 Correct 67 ms 2028 KB Output is correct
10 Correct 140 ms 852 KB Output is correct
11 Correct 445 ms 31540 KB Output is correct
12 Correct 1012 ms 2636 KB Output is correct
13 Execution timed out 2065 ms 15988 KB Time limit exceeded
14 Execution timed out 2067 ms 10948 KB Time limit exceeded
15 Execution timed out 2061 ms 11172 KB Time limit exceeded
16 Execution timed out 2039 ms 7744 KB Time limit exceeded
17 Execution timed out 2050 ms 22604 KB Time limit exceeded
18 Execution timed out 2067 ms 21328 KB Time limit exceeded
19 Execution timed out 2063 ms 39260 KB Time limit exceeded
20 Execution timed out 2064 ms 18392 KB Time limit exceeded
21 Execution timed out 2060 ms 34304 KB Time limit exceeded
22 Execution timed out 2073 ms 33252 KB Time limit exceeded
23 Execution timed out 2066 ms 29428 KB Time limit exceeded
24 Execution timed out 2039 ms 34176 KB Time limit exceeded
25 Execution timed out 2071 ms 48092 KB Time limit exceeded
26 Runtime error 610 ms 1048576 KB Execution killed with signal 9
27 Runtime error 935 ms 1048576 KB Execution killed with signal 9
28 Runtime error 970 ms 1048576 KB Execution killed with signal 9
29 Runtime error 944 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1054 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2091 ms 358276 KB Time limit exceeded
32 Runtime error 634 ms 1048576 KB Execution killed with signal 9