oj.uz

Submission #811140

# Submission time Handle Problem Language Result Execution time Memory
811140 2023-08-07T01:06:31 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 200 ms 27112 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 29 ms 21088 KB Output is correct
5 Correct 31 ms 3604 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 1104 KB Output is correct
10 Correct 26 ms 2564 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 37 ms 9940 KB Output is correct
13 Correct 31 ms 3668 KB Output is correct
14 Correct 31 ms 3664 KB Output is correct
15 Correct 213 ms 8780 KB Output is correct
16 Correct 183 ms 27040 KB Output is correct
17 Correct 233 ms 10320 KB Output is correct
18 Correct 24 ms 21004 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1315 ms 31568 KB Output is correct
2 Execution timed out 2079 ms 15940 KB Time limit exceeded
3 Execution timed out 2075 ms 37020 KB Time limit exceeded
4 Execution timed out 2062 ms 39800 KB Time limit exceeded
5 Execution timed out 2047 ms 29336 KB Time limit exceeded
6 Runtime error 1042 ms 1048576 KB Execution killed with signal 9
7 Correct 1268 ms 32420 KB Output is correct
8 Correct 1455 ms 31532 KB Output is correct
9 Correct 67 ms 2064 KB Output is correct
10 Correct 137 ms 864 KB Output is correct
11 Correct 531 ms 31668 KB Output is correct
12 Correct 1076 ms 2824 KB Output is correct
13 Execution timed out 2072 ms 15140 KB Time limit exceeded
14 Execution timed out 2061 ms 10720 KB Time limit exceeded
15 Execution timed out 2077 ms 10784 KB Time limit exceeded
16 Execution timed out 2066 ms 7844 KB Time limit exceeded
17 Execution timed out 2066 ms 19208 KB Time limit exceeded
18 Execution timed out 2062 ms 18072 KB Time limit exceeded
19 Execution timed out 2070 ms 36752 KB Time limit exceeded
20 Execution timed out 2054 ms 15680 KB Time limit exceeded
21 Execution timed out 2025 ms 26524 KB Time limit exceeded
22 Execution timed out 2064 ms 25772 KB Time limit exceeded
23 Execution timed out 2021 ms 23100 KB Time limit exceeded
24 Execution timed out 2085 ms 26564 KB Time limit exceeded
25 Execution timed out 2090 ms 33856 KB Time limit exceeded
26 Runtime error 636 ms 1048576 KB Execution killed with signal 9
27 Runtime error 972 ms 1048576 KB Execution killed with signal 9
28 Runtime error 977 ms 1048576 KB Execution killed with signal 9
29 Runtime error 969 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1150 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2089 ms 337312 KB Time limit exceeded
32 Runtime error 630 ms 1048576 KB Execution killed with signal 9