oj.uz

Submission #811243

# Submission time Handle Problem Language Result Execution time Memory
811243 2023-08-07T03:02:07 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 178 ms 26800 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 20916 KB Output is correct
5 Correct 31 ms 3512 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 1 ms 1180 KB Output is correct
10 Correct 26 ms 2508 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9800 KB Output is correct
13 Correct 31 ms 3540 KB Output is correct
14 Correct 30 ms 3540 KB Output is correct
15 Correct 210 ms 8512 KB Output is correct
16 Correct 209 ms 26816 KB Output is correct
17 Correct 216 ms 10088 KB Output is correct
18 Correct 23 ms 20948 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1326 ms 31336 KB Output is correct
2 Execution timed out 2074 ms 14412 KB Time limit exceeded
3 Execution timed out 2090 ms 32464 KB Time limit exceeded
4 Execution timed out 2080 ms 36156 KB Time limit exceeded
5 Execution timed out 2079 ms 24484 KB Time limit exceeded
6 Runtime error 999 ms 1048576 KB Execution killed with signal 9
7 Correct 1217 ms 32252 KB Output is correct
8 Correct 1475 ms 31400 KB Output is correct
9 Correct 67 ms 2008 KB Output is correct
10 Correct 140 ms 848 KB Output is correct
11 Correct 496 ms 31484 KB Output is correct
12 Correct 968 ms 2600 KB Output is correct
13 Execution timed out 2070 ms 14472 KB Time limit exceeded
14 Execution timed out 2094 ms 10048 KB Time limit exceeded
15 Execution timed out 2089 ms 10104 KB Time limit exceeded
16 Execution timed out 2087 ms 7288 KB Time limit exceeded
17 Execution timed out 2041 ms 18520 KB Time limit exceeded
18 Execution timed out 2055 ms 17328 KB Time limit exceeded
19 Execution timed out 2061 ms 36052 KB Time limit exceeded
20 Execution timed out 2068 ms 15076 KB Time limit exceeded
21 Execution timed out 2088 ms 25220 KB Time limit exceeded
22 Execution timed out 2087 ms 24488 KB Time limit exceeded
23 Execution timed out 2070 ms 21896 KB Time limit exceeded
24 Execution timed out 2071 ms 25292 KB Time limit exceeded
25 Execution timed out 2063 ms 32460 KB Time limit exceeded
26 Runtime error 613 ms 1048576 KB Execution killed with signal 9
27 Runtime error 934 ms 1048576 KB Execution killed with signal 9
28 Runtime error 998 ms 1048576 KB Execution killed with signal 9
29 Runtime error 932 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1091 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2072 ms 337316 KB Time limit exceeded
32 Runtime error 627 ms 1048576 KB Execution killed with signal 9