oj.uz

Submission #811254

# Submission time Handle Problem Language Result Execution time Memory
811254 2023-08-07T03:16:27 Z kebine 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 179 ms 26768 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 21 ms 20948 KB Output is correct
5 Correct 30 ms 3524 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 1108 KB Output is correct
10 Correct 26 ms 2528 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9864 KB Output is correct
13 Correct 32 ms 3540 KB Output is correct
14 Correct 31 ms 3592 KB Output is correct
15 Correct 215 ms 8424 KB Output is correct
16 Correct 176 ms 26780 KB Output is correct
17 Correct 214 ms 10004 KB Output is correct
18 Correct 21 ms 20916 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 31392 KB Output is correct
2 Execution timed out 2061 ms 14596 KB Time limit exceeded
3 Execution timed out 2075 ms 32460 KB Time limit exceeded
4 Execution timed out 2078 ms 36452 KB Time limit exceeded
5 Execution timed out 2087 ms 24488 KB Time limit exceeded
6 Runtime error 1038 ms 1048576 KB Execution killed with signal 9
7 Correct 1259 ms 32300 KB Output is correct
8 Correct 1405 ms 31380 KB Output is correct
9 Correct 67 ms 2004 KB Output is correct
10 Correct 138 ms 852 KB Output is correct
11 Correct 518 ms 31536 KB Output is correct
12 Correct 981 ms 2836 KB Output is correct
13 Execution timed out 2062 ms 15056 KB Time limit exceeded
14 Execution timed out 2057 ms 10464 KB Time limit exceeded
15 Execution timed out 2055 ms 10324 KB Time limit exceeded
16 Execution timed out 2033 ms 7500 KB Time limit exceeded
17 Execution timed out 2017 ms 19192 KB Time limit exceeded
18 Execution timed out 2021 ms 18072 KB Time limit exceeded
19 Execution timed out 2033 ms 36488 KB Time limit exceeded
20 Execution timed out 2021 ms 15640 KB Time limit exceeded
21 Execution timed out 2102 ms 26072 KB Time limit exceeded
22 Execution timed out 2084 ms 25384 KB Time limit exceeded
23 Execution timed out 2103 ms 22712 KB Time limit exceeded
24 Execution timed out 2078 ms 26184 KB Time limit exceeded
25 Execution timed out 2072 ms 33312 KB Time limit exceeded
26 Runtime error 707 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1160 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1061 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1010 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1124 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2066 ms 338600 KB Time limit exceeded
32 Runtime error 685 ms 1048576 KB Execution killed with signal 9