oj.uz

Submission #811238

# Submission time Handle Problem Language Result Execution time Memory
811238 2023-08-07T02:57:51 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 179 ms 26744 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 23 ms 20968 KB Output is correct
5 Correct 31 ms 3552 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 2496 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 36 ms 9856 KB Output is correct
13 Correct 31 ms 3604 KB Output is correct
14 Correct 31 ms 3556 KB Output is correct
15 Correct 212 ms 8460 KB Output is correct
16 Correct 183 ms 26816 KB Output is correct
17 Correct 219 ms 10088 KB Output is correct
18 Correct 24 ms 20872 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1558 ms 31412 KB Output is correct
2 Execution timed out 2060 ms 14536 KB Time limit exceeded
3 Execution timed out 2049 ms 34504 KB Time limit exceeded
4 Execution timed out 2080 ms 36200 KB Time limit exceeded
5 Execution timed out 2077 ms 26664 KB Time limit exceeded
6 Runtime error 996 ms 1048576 KB Execution killed with signal 9
7 Correct 1398 ms 32360 KB Output is correct
8 Correct 1330 ms 31400 KB Output is correct
9 Correct 71 ms 2004 KB Output is correct
10 Correct 140 ms 824 KB Output is correct
11 Correct 502 ms 31484 KB Output is correct
12 Correct 1018 ms 2736 KB Output is correct
13 Execution timed out 2073 ms 14596 KB Time limit exceeded
14 Execution timed out 2086 ms 10092 KB Time limit exceeded
15 Execution timed out 2069 ms 10020 KB Time limit exceeded
16 Execution timed out 2076 ms 7308 KB Time limit exceeded
17 Execution timed out 2045 ms 18776 KB Time limit exceeded
18 Execution timed out 2039 ms 17544 KB Time limit exceeded
19 Execution timed out 2052 ms 36160 KB Time limit exceeded
20 Execution timed out 2061 ms 15180 KB Time limit exceeded
21 Execution timed out 2048 ms 25520 KB Time limit exceeded
22 Execution timed out 2013 ms 24748 KB Time limit exceeded
23 Execution timed out 2065 ms 22104 KB Time limit exceeded
24 Execution timed out 2059 ms 25528 KB Time limit exceeded
25 Execution timed out 2045 ms 32792 KB Time limit exceeded
26 Runtime error 637 ms 1048576 KB Execution killed with signal 9
27 Runtime error 972 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1114 ms 1048576 KB Execution killed with signal 9
29 Runtime error 957 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1085 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2089 ms 348276 KB Time limit exceeded
32 Runtime error 643 ms 1048576 KB Execution killed with signal 9