oj.uz

Submission #811275

# Submission time Handle Problem Language Result Execution time Memory
811275 2023-08-07T03:36:40 Z andecaandeci 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 205 ms 27076 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 28 ms 21088 KB Output is correct
5 Correct 31 ms 3616 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 28 ms 2568 KB Output is correct
11 Correct 8 ms 6228 KB Output is correct
12 Correct 36 ms 9928 KB Output is correct
13 Correct 31 ms 3680 KB Output is correct
14 Correct 31 ms 3660 KB Output is correct
15 Correct 216 ms 8788 KB Output is correct
16 Correct 199 ms 27180 KB Output is correct
17 Correct 218 ms 10244 KB Output is correct
18 Correct 35 ms 21068 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1520 ms 31400 KB Output is correct
2 Execution timed out 2064 ms 15944 KB Time limit exceeded
3 Execution timed out 2017 ms 38104 KB Time limit exceeded
4 Execution timed out 2060 ms 38752 KB Time limit exceeded
5 Execution timed out 2082 ms 30128 KB Time limit exceeded
6 Runtime error 1032 ms 1048576 KB Execution killed with signal 9
7 Correct 1337 ms 32348 KB Output is correct
8 Correct 1575 ms 31428 KB Output is correct
9 Correct 67 ms 2008 KB Output is correct
10 Correct 142 ms 868 KB Output is correct
11 Correct 570 ms 31496 KB Output is correct
12 Correct 1018 ms 2596 KB Output is correct
13 Execution timed out 2086 ms 14464 KB Time limit exceeded
14 Execution timed out 2066 ms 10080 KB Time limit exceeded
15 Execution timed out 2084 ms 9968 KB Time limit exceeded
16 Execution timed out 2081 ms 7208 KB Time limit exceeded
17 Execution timed out 2071 ms 18500 KB Time limit exceeded
18 Execution timed out 2076 ms 17308 KB Time limit exceeded
19 Execution timed out 2083 ms 36428 KB Time limit exceeded
20 Execution timed out 2073 ms 15400 KB Time limit exceeded
21 Execution timed out 2083 ms 25988 KB Time limit exceeded
22 Execution timed out 2021 ms 25256 KB Time limit exceeded
23 Execution timed out 2052 ms 22808 KB Time limit exceeded
24 Execution timed out 2025 ms 26304 KB Time limit exceeded
25 Execution timed out 2090 ms 33500 KB Time limit exceeded
26 Runtime error 667 ms 1048576 KB Execution killed with signal 9
27 Runtime error 968 ms 1048576 KB Execution killed with signal 9
28 Runtime error 989 ms 1048576 KB Execution killed with signal 9
29 Runtime error 969 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1219 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2094 ms 348336 KB Time limit exceeded
32 Runtime error 657 ms 1048576 KB Execution killed with signal 9