oj.uz

Submission #811219

# Submission time Handle Problem Language Result Execution time Memory
811219 2023-08-07T02:38:33 Z kebine 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 182 ms 26784 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 25 ms 20908 KB Output is correct
5 Correct 32 ms 3556 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 1 ms 1108 KB Output is correct
10 Correct 26 ms 2504 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 36 ms 9836 KB Output is correct
13 Correct 30 ms 3600 KB Output is correct
14 Correct 30 ms 3580 KB Output is correct
15 Correct 213 ms 8548 KB Output is correct
16 Correct 181 ms 26832 KB Output is correct
17 Correct 216 ms 10024 KB Output is correct
18 Correct 22 ms 20948 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 31548 KB Output is correct
2 Execution timed out 2061 ms 14540 KB Time limit exceeded
3 Execution timed out 2068 ms 32488 KB Time limit exceeded
4 Execution timed out 2065 ms 36428 KB Time limit exceeded
5 Execution timed out 2075 ms 24548 KB Time limit exceeded
6 Runtime error 939 ms 1048576 KB Execution killed with signal 9
7 Correct 1111 ms 32232 KB Output is correct
8 Correct 1341 ms 31416 KB Output is correct
9 Correct 102 ms 2008 KB Output is correct
10 Correct 226 ms 828 KB Output is correct
11 Correct 447 ms 31492 KB Output is correct
12 Correct 964 ms 2664 KB Output is correct
13 Execution timed out 2053 ms 14692 KB Time limit exceeded
14 Execution timed out 2066 ms 9956 KB Time limit exceeded
15 Execution timed out 2059 ms 9928 KB Time limit exceeded
16 Execution timed out 2077 ms 7180 KB Time limit exceeded
17 Execution timed out 2067 ms 17684 KB Time limit exceeded
18 Execution timed out 2066 ms 17368 KB Time limit exceeded
19 Execution timed out 2073 ms 35220 KB Time limit exceeded
20 Execution timed out 2081 ms 14988 KB Time limit exceeded
21 Execution timed out 2077 ms 25204 KB Time limit exceeded
22 Execution timed out 2087 ms 24484 KB Time limit exceeded
23 Execution timed out 2082 ms 21804 KB Time limit exceeded
24 Execution timed out 2067 ms 25300 KB Time limit exceeded
25 Execution timed out 2071 ms 32424 KB Time limit exceeded
26 Runtime error 623 ms 1048576 KB Execution killed with signal 9
27 Runtime error 922 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1025 ms 1048576 KB Execution killed with signal 9
29 Runtime error 991 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1091 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2101 ms 337320 KB Time limit exceeded
32 Runtime error 791 ms 1048576 KB Execution killed with signal 9