oj.uz

Submission #813073

# Submission time Handle Problem Language Result Execution time Memory
813073 2023-08-07T13:09:22 Z andecaandeci 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 219 ms 27020 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 21112 KB Output is correct
5 Correct 35 ms 3660 KB Output is correct
6 Correct 1 ms 452 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 27 ms 2572 KB Output is correct
11 Correct 5 ms 6232 KB Output is correct
12 Correct 37 ms 9880 KB Output is correct
13 Correct 31 ms 3572 KB Output is correct
14 Correct 31 ms 3624 KB Output is correct
15 Correct 259 ms 8792 KB Output is correct
16 Correct 179 ms 27072 KB Output is correct
17 Correct 215 ms 10244 KB Output is correct
18 Correct 25 ms 21036 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 31408 KB Output is correct
2 Execution timed out 2068 ms 15984 KB Time limit exceeded
3 Execution timed out 2068 ms 37320 KB Time limit exceeded
4 Execution timed out 2060 ms 39112 KB Time limit exceeded
5 Execution timed out 2088 ms 29344 KB Time limit exceeded
6 Runtime error 977 ms 1048576 KB Execution killed with signal 9
7 Correct 1235 ms 32364 KB Output is correct
8 Correct 1401 ms 31492 KB Output is correct
9 Correct 70 ms 2068 KB Output is correct
10 Correct 141 ms 852 KB Output is correct
11 Correct 507 ms 31536 KB Output is correct
12 Correct 969 ms 2728 KB Output is correct
13 Execution timed out 2077 ms 15940 KB Time limit exceeded
14 Execution timed out 2029 ms 10960 KB Time limit exceeded
15 Execution timed out 2079 ms 10924 KB Time limit exceeded
16 Execution timed out 2065 ms 7812 KB Time limit exceeded
17 Execution timed out 2041 ms 21964 KB Time limit exceeded
18 Execution timed out 2055 ms 20636 KB Time limit exceeded
19 Execution timed out 2041 ms 39088 KB Time limit exceeded
20 Execution timed out 2064 ms 18320 KB Time limit exceeded
21 Execution timed out 2019 ms 30092 KB Time limit exceeded
22 Execution timed out 2099 ms 29488 KB Time limit exceeded
23 Execution timed out 2005 ms 26152 KB Time limit exceeded
24 Execution timed out 2095 ms 30228 KB Time limit exceeded
25 Execution timed out 2090 ms 37200 KB Time limit exceeded
26 Runtime error 598 ms 1048576 KB Execution killed with signal 9
27 Runtime error 933 ms 1048576 KB Execution killed with signal 9
28 Runtime error 985 ms 1048576 KB Execution killed with signal 9
29 Runtime error 914 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1052 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2087 ms 353032 KB Time limit exceeded
32 Runtime error 630 ms 1048576 KB Execution killed with signal 9