oj.uz

Submission #811576

# Submission time Handle Problem Language Result Execution time Memory
811576 2023-08-07T04:58:49 Z andecaandeci 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 209 ms 26728 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 24 ms 20904 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 2500 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 40 ms 9844 KB Output is correct
13 Correct 31 ms 3600 KB Output is correct
14 Correct 42 ms 3584 KB Output is correct
15 Correct 312 ms 8544 KB Output is correct
16 Correct 216 ms 26832 KB Output is correct
17 Correct 228 ms 10088 KB Output is correct
18 Correct 22 ms 20920 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 31396 KB Output is correct
2 Execution timed out 2085 ms 14348 KB Time limit exceeded
3 Execution timed out 2080 ms 32456 KB Time limit exceeded
4 Execution timed out 2072 ms 36212 KB Time limit exceeded
5 Execution timed out 2067 ms 24524 KB Time limit exceeded
6 Runtime error 1055 ms 1048576 KB Execution killed with signal 9
7 Correct 1336 ms 32404 KB Output is correct
8 Correct 1490 ms 31444 KB Output is correct
9 Correct 70 ms 2068 KB Output is correct
10 Correct 139 ms 940 KB Output is correct
11 Correct 497 ms 31536 KB Output is correct
12 Correct 1002 ms 2732 KB Output is correct
13 Execution timed out 2053 ms 14612 KB Time limit exceeded
14 Execution timed out 2076 ms 10360 KB Time limit exceeded
15 Execution timed out 2059 ms 10204 KB Time limit exceeded
16 Execution timed out 2079 ms 7244 KB Time limit exceeded
17 Execution timed out 2056 ms 18780 KB Time limit exceeded
18 Execution timed out 2058 ms 17532 KB Time limit exceeded
19 Execution timed out 2067 ms 36148 KB Time limit exceeded
20 Execution timed out 2060 ms 15268 KB Time limit exceeded
21 Execution timed out 2033 ms 25664 KB Time limit exceeded
22 Execution timed out 2048 ms 24824 KB Time limit exceeded
23 Execution timed out 2060 ms 21960 KB Time limit exceeded
24 Execution timed out 2073 ms 25676 KB Time limit exceeded
25 Execution timed out 2012 ms 33004 KB Time limit exceeded
26 Runtime error 616 ms 1048576 KB Execution killed with signal 9
27 Runtime error 924 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1063 ms 1048576 KB Execution killed with signal 9
29 Runtime error 936 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1095 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2041 ms 337696 KB Time limit exceeded
32 Runtime error 643 ms 1048576 KB Execution killed with signal 9