oj.uz

Submission #811136

# Submission time Handle Problem Language Result Execution time Memory
811136 2023-08-07T01:04:18 Z makanhulia Tracks in the Snow (BOI13_tracks) C++17
43.125 / 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 178 ms 26956 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 27 ms 21100 KB Output is correct
5 Correct 32 ms 3668 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 42 ms 2568 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 39 ms 9924 KB Output is correct
13 Correct 33 ms 3664 KB Output is correct
14 Correct 42 ms 3660 KB Output is correct
15 Correct 261 ms 8776 KB Output is correct
16 Correct 212 ms 27072 KB Output is correct
17 Correct 246 ms 10256 KB Output is correct
18 Correct 27 ms 21096 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1605 ms 31428 KB Output is correct
2 Execution timed out 2053 ms 15992 KB Time limit exceeded
3 Execution timed out 2101 ms 33984 KB Time limit exceeded
4 Execution timed out 2041 ms 37356 KB Time limit exceeded
5 Execution timed out 2015 ms 26156 KB Time limit exceeded
6 Runtime error 1165 ms 1048576 KB Execution killed with signal 9
7 Correct 1484 ms 32392 KB Output is correct
8 Execution timed out 2079 ms 31460 KB Time limit exceeded
9 Correct 69 ms 2004 KB Output is correct
10 Correct 143 ms 864 KB Output is correct
11 Correct 678 ms 31540 KB Output is correct
12 Correct 1022 ms 2676 KB Output is correct
13 Execution timed out 2060 ms 15876 KB Time limit exceeded
14 Execution timed out 2069 ms 10988 KB Time limit exceeded
15 Execution timed out 2067 ms 10688 KB Time limit exceeded
16 Execution timed out 2067 ms 7772 KB Time limit exceeded
17 Execution timed out 2062 ms 22552 KB Time limit exceeded
18 Execution timed out 2043 ms 21136 KB Time limit exceeded
19 Execution timed out 2009 ms 38864 KB Time limit exceeded
20 Execution timed out 2066 ms 18356 KB Time limit exceeded
21 Execution timed out 2054 ms 29060 KB Time limit exceeded
22 Execution timed out 2071 ms 28544 KB Time limit exceeded
23 Execution timed out 2100 ms 26148 KB Time limit exceeded
24 Execution timed out 2069 ms 29264 KB Time limit exceeded
25 Execution timed out 2011 ms 36368 KB Time limit exceeded
26 Runtime error 646 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1066 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1074 ms 1048576 KB Execution killed with signal 9
29 Runtime error 976 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1103 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2100 ms 343348 KB Time limit exceeded
32 Runtime error 645 ms 1048576 KB Execution killed with signal 9