oj.uz

Submission #811168

# Submission time Handle Problem Language Result Execution time Memory
811168 2023-08-07T01:40:07 Z christinelynn 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 26960 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 21076 KB Output is correct
5 Correct 31 ms 3632 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 2560 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 36 ms 9964 KB Output is correct
13 Correct 31 ms 3620 KB Output is correct
14 Correct 30 ms 3612 KB Output is correct
15 Correct 212 ms 8544 KB Output is correct
16 Correct 182 ms 26884 KB Output is correct
17 Correct 228 ms 10292 KB Output is correct
18 Correct 26 ms 21076 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 31444 KB Output is correct
2 Execution timed out 2074 ms 14728 KB Time limit exceeded
3 Execution timed out 2058 ms 32728 KB Time limit exceeded
4 Execution timed out 2074 ms 36476 KB Time limit exceeded
5 Execution timed out 2057 ms 24828 KB Time limit exceeded
6 Runtime error 1022 ms 1048576 KB Execution killed with signal 9
7 Correct 1138 ms 32408 KB Output is correct
8 Correct 1293 ms 31508 KB Output is correct
9 Correct 66 ms 2020 KB Output is correct
10 Correct 137 ms 852 KB Output is correct
11 Correct 462 ms 31540 KB Output is correct
12 Correct 964 ms 2796 KB Output is correct
13 Execution timed out 2072 ms 14768 KB Time limit exceeded
14 Execution timed out 2071 ms 10408 KB Time limit exceeded
15 Execution timed out 2073 ms 10288 KB Time limit exceeded
16 Execution timed out 2045 ms 7336 KB Time limit exceeded
17 Execution timed out 2068 ms 19028 KB Time limit exceeded
18 Execution timed out 2009 ms 17660 KB Time limit exceeded
19 Execution timed out 2073 ms 36664 KB Time limit exceeded
20 Execution timed out 2059 ms 15384 KB Time limit exceeded
21 Execution timed out 2048 ms 25604 KB Time limit exceeded
22 Execution timed out 2084 ms 25000 KB Time limit exceeded
23 Execution timed out 2036 ms 22452 KB Time limit exceeded
24 Execution timed out 2053 ms 25748 KB Time limit exceeded
25 Execution timed out 2056 ms 32820 KB Time limit exceeded
26 Runtime error 591 ms 1048576 KB Execution killed with signal 9
27 Runtime error 913 ms 1048576 KB Execution killed with signal 9
28 Runtime error 957 ms 1048576 KB Execution killed with signal 9
29 Runtime error 920 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1062 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2092 ms 351348 KB Time limit exceeded
32 Runtime error 607 ms 1048576 KB Execution killed with signal 9