oj.uz

Submission #811236

# Submission time Handle Problem Language Result Execution time Memory
811236 2023-08-07T02:56:51 Z devariaota 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 203 ms 26828 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 27 ms 20956 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 26 ms 2516 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9800 KB Output is correct
13 Correct 43 ms 3592 KB Output is correct
14 Correct 31 ms 3576 KB Output is correct
15 Correct 223 ms 8548 KB Output is correct
16 Correct 184 ms 26772 KB Output is correct
17 Correct 225 ms 10060 KB Output is correct
18 Correct 24 ms 20948 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1310 ms 31360 KB Output is correct
2 Execution timed out 2060 ms 14456 KB Time limit exceeded
3 Execution timed out 2073 ms 32528 KB Time limit exceeded
4 Execution timed out 2066 ms 35224 KB Time limit exceeded
5 Execution timed out 2085 ms 24484 KB Time limit exceeded
6 Runtime error 1173 ms 1048576 KB Execution killed with signal 9
7 Correct 1179 ms 32352 KB Output is correct
8 Correct 1469 ms 31504 KB Output is correct
9 Correct 67 ms 2004 KB Output is correct
10 Correct 230 ms 900 KB Output is correct
11 Correct 540 ms 31492 KB Output is correct
12 Correct 1057 ms 2592 KB Output is correct
13 Execution timed out 2029 ms 14972 KB Time limit exceeded
14 Execution timed out 2050 ms 10088 KB Time limit exceeded
15 Execution timed out 2085 ms 9852 KB Time limit exceeded
16 Execution timed out 2072 ms 7180 KB Time limit exceeded
17 Execution timed out 2073 ms 20292 KB Time limit exceeded
18 Execution timed out 2045 ms 19056 KB Time limit exceeded
19 Execution timed out 2052 ms 37608 KB Time limit exceeded
20 Execution timed out 2056 ms 15024 KB Time limit exceeded
21 Execution timed out 2072 ms 25292 KB Time limit exceeded
22 Execution timed out 2088 ms 24488 KB Time limit exceeded
23 Execution timed out 2081 ms 21768 KB Time limit exceeded
24 Execution timed out 2091 ms 25292 KB Time limit exceeded
25 Execution timed out 2059 ms 32496 KB Time limit exceeded
26 Runtime error 643 ms 1048576 KB Execution killed with signal 9
27 Runtime error 952 ms 1048576 KB Execution killed with signal 9
28 Runtime error 975 ms 1048576 KB Execution killed with signal 9
29 Runtime error 944 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1117 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2068 ms 348584 KB Time limit exceeded
32 Runtime error 658 ms 1048576 KB Execution killed with signal 9