oj.uz

Submission #811159

# Submission time Handle Problem Language Result Execution time Memory
811159 2023-08-07T01:25:35 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 196 ms 26824 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 32 ms 21048 KB Output is correct
5 Correct 31 ms 3540 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 43 ms 2496 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9800 KB Output is correct
13 Correct 31 ms 3544 KB Output is correct
14 Correct 45 ms 3520 KB Output is correct
15 Correct 245 ms 8592 KB Output is correct
16 Correct 197 ms 26780 KB Output is correct
17 Correct 242 ms 10068 KB Output is correct
18 Correct 26 ms 20944 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 31416 KB Output is correct
2 Execution timed out 2076 ms 14472 KB Time limit exceeded
3 Execution timed out 2079 ms 32500 KB Time limit exceeded
4 Execution timed out 2088 ms 35376 KB Time limit exceeded
5 Execution timed out 2070 ms 24384 KB Time limit exceeded
6 Runtime error 1002 ms 1048576 KB Execution killed with signal 9
7 Correct 1198 ms 32408 KB Output is correct
8 Correct 1371 ms 31384 KB Output is correct
9 Correct 70 ms 2004 KB Output is correct
10 Correct 140 ms 824 KB Output is correct
11 Correct 483 ms 31504 KB Output is correct
12 Correct 1018 ms 2676 KB Output is correct
13 Execution timed out 2069 ms 14460 KB Time limit exceeded
14 Execution timed out 2071 ms 10092 KB Time limit exceeded
15 Execution timed out 2065 ms 9952 KB Time limit exceeded
16 Execution timed out 2054 ms 7232 KB Time limit exceeded
17 Execution timed out 2074 ms 18500 KB Time limit exceeded
18 Execution timed out 2048 ms 17352 KB Time limit exceeded
19 Execution timed out 2082 ms 35108 KB Time limit exceeded
20 Execution timed out 2093 ms 14988 KB Time limit exceeded
21 Execution timed out 2079 ms 25332 KB Time limit exceeded
22 Execution timed out 2066 ms 24468 KB Time limit exceeded
23 Execution timed out 2074 ms 21784 KB Time limit exceeded
24 Execution timed out 2083 ms 25308 KB Time limit exceeded
25 Execution timed out 2067 ms 32700 KB Time limit exceeded
26 Runtime error 593 ms 1048576 KB Execution killed with signal 9
27 Runtime error 889 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1018 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1238 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1161 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2069 ms 331360 KB Time limit exceeded
32 Runtime error 832 ms 1048576 KB Execution killed with signal 9