oj.uz

Submission #811213

# Submission time Handle Problem Language Result Execution time Memory
811213 2023-08-07T02:35:15 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 183 ms 27032 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 22 ms 21100 KB Output is correct
5 Correct 31 ms 3644 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 2516 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9884 KB Output is correct
13 Correct 33 ms 3676 KB Output is correct
14 Correct 31 ms 3660 KB Output is correct
15 Correct 211 ms 8776 KB Output is correct
16 Correct 187 ms 27036 KB Output is correct
17 Correct 215 ms 10296 KB Output is correct
18 Correct 23 ms 21076 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 31516 KB Output is correct
2 Execution timed out 2072 ms 14828 KB Time limit exceeded
3 Execution timed out 2049 ms 32972 KB Time limit exceeded
4 Execution timed out 2070 ms 36044 KB Time limit exceeded
5 Execution timed out 2056 ms 24804 KB Time limit exceeded
6 Runtime error 1108 ms 1048576 KB Execution killed with signal 9
7 Correct 1190 ms 32392 KB Output is correct
8 Correct 1365 ms 31460 KB Output is correct
9 Correct 67 ms 2064 KB Output is correct
10 Correct 152 ms 856 KB Output is correct
11 Correct 465 ms 31532 KB Output is correct
12 Correct 1012 ms 2656 KB Output is correct
13 Execution timed out 2065 ms 14852 KB Time limit exceeded
14 Execution timed out 2047 ms 10456 KB Time limit exceeded
15 Execution timed out 2065 ms 10428 KB Time limit exceeded
16 Execution timed out 2043 ms 7464 KB Time limit exceeded
17 Execution timed out 2068 ms 18908 KB Time limit exceeded
18 Execution timed out 2033 ms 17876 KB Time limit exceeded
19 Execution timed out 2077 ms 36572 KB Time limit exceeded
20 Execution timed out 2074 ms 15464 KB Time limit exceeded
21 Execution timed out 2032 ms 25776 KB Time limit exceeded
22 Execution timed out 2096 ms 25104 KB Time limit exceeded
23 Execution timed out 2041 ms 22364 KB Time limit exceeded
24 Execution timed out 2056 ms 25864 KB Time limit exceeded
25 Execution timed out 2021 ms 32972 KB Time limit exceeded
26 Runtime error 590 ms 1048576 KB Execution killed with signal 9
27 Runtime error 899 ms 1048576 KB Execution killed with signal 9
28 Runtime error 954 ms 1048576 KB Execution killed with signal 9
29 Runtime error 928 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1046 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2053 ms 348784 KB Time limit exceeded
32 Runtime error 611 ms 1048576 KB Execution killed with signal 9