oj.uz

Submission #811372

# Submission time Handle Problem Language Result Execution time Memory
811372 2023-08-07T04:13:21 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 199 ms 27200 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 22 ms 21088 KB Output is correct
5 Correct 31 ms 3636 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 2556 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9940 KB Output is correct
13 Correct 31 ms 3660 KB Output is correct
14 Correct 30 ms 3668 KB Output is correct
15 Correct 221 ms 8808 KB Output is correct
16 Correct 185 ms 27008 KB Output is correct
17 Correct 217 ms 10304 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 1397 ms 31476 KB Output is correct
2 Execution timed out 2059 ms 15888 KB Time limit exceeded
3 Execution timed out 2087 ms 38164 KB Time limit exceeded
4 Execution timed out 2019 ms 38232 KB Time limit exceeded
5 Execution timed out 2052 ms 28452 KB Time limit exceeded
6 Runtime error 1171 ms 1048576 KB Execution killed with signal 9
7 Correct 1487 ms 32400 KB Output is correct
8 Correct 1707 ms 31432 KB Output is correct
9 Correct 91 ms 2000 KB Output is correct
10 Correct 206 ms 856 KB Output is correct
11 Correct 569 ms 31552 KB Output is correct
12 Correct 1126 ms 2716 KB Output is correct
13 Execution timed out 2061 ms 15984 KB Time limit exceeded
14 Execution timed out 2068 ms 10976 KB Time limit exceeded
15 Execution timed out 2053 ms 10664 KB Time limit exceeded
16 Execution timed out 2067 ms 7780 KB Time limit exceeded
17 Execution timed out 2021 ms 18592 KB Time limit exceeded
18 Execution timed out 2065 ms 17368 KB Time limit exceeded
19 Execution timed out 2072 ms 35720 KB Time limit exceeded
20 Execution timed out 2084 ms 14992 KB Time limit exceeded
21 Execution timed out 2062 ms 25236 KB Time limit exceeded
22 Execution timed out 2080 ms 24488 KB Time limit exceeded
23 Execution timed out 2091 ms 21828 KB Time limit exceeded
24 Execution timed out 2017 ms 25292 KB Time limit exceeded
25 Execution timed out 2082 ms 32472 KB Time limit exceeded
26 Runtime error 668 ms 1048576 KB Execution killed with signal 9
27 Runtime error 958 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1010 ms 1048576 KB Execution killed with signal 9
29 Runtime error 972 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1081 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2072 ms 337320 KB Time limit exceeded
32 Runtime error 631 ms 1048576 KB Execution killed with signal 9