oj.uz

Submission #811135

# Submission time Handle Problem Language Result Execution time Memory
811135 2023-08-07T01:02:59 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 198 ms 27044 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 25 ms 20992 KB Output is correct
5 Correct 31 ms 3600 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 1228 KB Output is correct
9 Correct 1 ms 1104 KB Output is correct
10 Correct 26 ms 2564 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 65 ms 9900 KB Output is correct
13 Correct 44 ms 3660 KB Output is correct
14 Correct 36 ms 3584 KB Output is correct
15 Correct 211 ms 8708 KB Output is correct
16 Correct 295 ms 27072 KB Output is correct
17 Correct 280 ms 10360 KB Output is correct
18 Correct 37 ms 21064 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1509 ms 31596 KB Output is correct
2 Execution timed out 2067 ms 14728 KB Time limit exceeded
3 Execution timed out 2041 ms 32848 KB Time limit exceeded
4 Execution timed out 2062 ms 36380 KB Time limit exceeded
5 Execution timed out 2028 ms 24940 KB Time limit exceeded
6 Runtime error 1327 ms 1048576 KB Execution killed with signal 9
7 Correct 1743 ms 32400 KB Output is correct
8 Correct 1747 ms 31376 KB Output is correct
9 Correct 66 ms 2000 KB Output is correct
10 Correct 138 ms 852 KB Output is correct
11 Correct 659 ms 31544 KB Output is correct
12 Correct 958 ms 2732 KB Output is correct
13 Execution timed out 2065 ms 15412 KB Time limit exceeded
14 Execution timed out 2072 ms 10932 KB Time limit exceeded
15 Execution timed out 2067 ms 10884 KB Time limit exceeded
16 Execution timed out 2077 ms 7856 KB Time limit exceeded
17 Execution timed out 2025 ms 19540 KB Time limit exceeded
18 Execution timed out 2037 ms 18176 KB Time limit exceeded
19 Execution timed out 2051 ms 36908 KB Time limit exceeded
20 Execution timed out 2040 ms 16012 KB Time limit exceeded
21 Execution timed out 2053 ms 25932 KB Time limit exceeded
22 Execution timed out 2086 ms 25356 KB Time limit exceeded
23 Execution timed out 2019 ms 22904 KB Time limit exceeded
24 Execution timed out 2011 ms 25996 KB Time limit exceeded
25 Execution timed out 2041 ms 33080 KB Time limit exceeded
26 Runtime error 652 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1004 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1002 ms 1048576 KB Execution killed with signal 9
29 Runtime error 943 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1132 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2037 ms 338072 KB Time limit exceeded
32 Runtime error 642 ms 1048576 KB Execution killed with signal 9