oj.uz

Submission #811925

# Submission time Handle Problem Language Result Execution time Memory
811925 2023-08-07T06:28:02 Z devariaota 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 212 ms 27072 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 23 ms 21068 KB Output is correct
5 Correct 30 ms 3592 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 27 ms 2560 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 36 ms 9852 KB Output is correct
13 Correct 30 ms 3624 KB Output is correct
14 Correct 31 ms 3692 KB Output is correct
15 Correct 214 ms 8792 KB Output is correct
16 Correct 179 ms 27040 KB Output is correct
17 Correct 215 ms 10272 KB Output is correct
18 Correct 30 ms 21068 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1251 ms 31444 KB Output is correct
2 Execution timed out 2069 ms 15996 KB Time limit exceeded
3 Execution timed out 2060 ms 47168 KB Time limit exceeded
4 Execution timed out 2085 ms 39780 KB Time limit exceeded
5 Execution timed out 2066 ms 33288 KB Time limit exceeded
6 Runtime error 1034 ms 1048576 KB Execution killed with signal 9
7 Correct 1453 ms 32396 KB Output is correct
8 Correct 1690 ms 31480 KB Output is correct
9 Correct 83 ms 2004 KB Output is correct
10 Correct 165 ms 860 KB Output is correct
11 Correct 604 ms 31540 KB Output is correct
12 Correct 1002 ms 2720 KB Output is correct
13 Execution timed out 2085 ms 16000 KB Time limit exceeded
14 Execution timed out 2083 ms 10964 KB Time limit exceeded
15 Execution timed out 2071 ms 10848 KB Time limit exceeded
16 Execution timed out 2065 ms 7836 KB Time limit exceeded
17 Execution timed out 2066 ms 22424 KB Time limit exceeded
18 Execution timed out 2053 ms 21148 KB Time limit exceeded
19 Execution timed out 2037 ms 39444 KB Time limit exceeded
20 Execution timed out 2058 ms 18364 KB Time limit exceeded
21 Execution timed out 2068 ms 34360 KB Time limit exceeded
22 Execution timed out 2054 ms 33228 KB Time limit exceeded
23 Execution timed out 2045 ms 29400 KB Time limit exceeded
24 Execution timed out 2071 ms 34272 KB Time limit exceeded
25 Execution timed out 2044 ms 43712 KB Time limit exceeded
26 Runtime error 681 ms 1048576 KB Execution killed with signal 9
27 Runtime error 999 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1036 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1002 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1169 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2060 ms 346704 KB Time limit exceeded
32 Runtime error 719 ms 1048576 KB Execution killed with signal 9