oj.uz

Submission #812149

# Submission time Handle Problem Language Result Execution time Memory
812149 2023-08-07T07:30:44 Z makanhulia 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 192 ms 27044 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 25 ms 21052 KB Output is correct
5 Correct 31 ms 3604 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 2 ms 1108 KB Output is correct
10 Correct 26 ms 2568 KB Output is correct
11 Correct 5 ms 6288 KB Output is correct
12 Correct 41 ms 9892 KB Output is correct
13 Correct 31 ms 3660 KB Output is correct
14 Correct 35 ms 3676 KB Output is correct
15 Correct 227 ms 8740 KB Output is correct
16 Correct 191 ms 27044 KB Output is correct
17 Correct 216 ms 10232 KB Output is correct
18 Correct 23 ms 21096 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1364 ms 31500 KB Output is correct
2 Execution timed out 2058 ms 16028 KB Time limit exceeded
3 Execution timed out 2008 ms 46704 KB Time limit exceeded
4 Execution timed out 2075 ms 39784 KB Time limit exceeded
5 Execution timed out 2076 ms 31880 KB Time limit exceeded
6 Runtime error 1059 ms 1048576 KB Execution killed with signal 9
7 Correct 1160 ms 32336 KB Output is correct
8 Correct 1374 ms 31468 KB Output is correct
9 Correct 67 ms 2004 KB Output is correct
10 Correct 148 ms 852 KB Output is correct
11 Correct 431 ms 31532 KB Output is correct
12 Correct 983 ms 2732 KB Output is correct
13 Execution timed out 2055 ms 15996 KB Time limit exceeded
14 Execution timed out 2077 ms 10748 KB Time limit exceeded
15 Execution timed out 2020 ms 10964 KB Time limit exceeded
16 Execution timed out 2057 ms 7844 KB Time limit exceeded
17 Execution timed out 2050 ms 22460 KB Time limit exceeded
18 Execution timed out 2067 ms 21096 KB Time limit exceeded
19 Execution timed out 2045 ms 39168 KB Time limit exceeded
20 Execution timed out 2074 ms 18396 KB Time limit exceeded
21 Execution timed out 2035 ms 32972 KB Time limit exceeded
22 Execution timed out 2028 ms 31748 KB Time limit exceeded
23 Execution timed out 2015 ms 28556 KB Time limit exceeded
24 Execution timed out 2012 ms 32764 KB Time limit exceeded
25 Execution timed out 2040 ms 46716 KB Time limit exceeded
26 Runtime error 667 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1016 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1018 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1016 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1082 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2060 ms 345948 KB Time limit exceeded
32 Runtime error 625 ms 1048576 KB Execution killed with signal 9