oj.uz

Submission #811134

# Submission time Handle Problem Language Result Execution time Memory
811134 2023-08-07T01:02:17 Z davinpwk Tracks in the Snow (BOI13_tracks) C++14
45.3125 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//* sol https://boi2013.informatik-olympiade.de/wp-content/uploads/2013/05/tracks-spoiler.pdf


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;
        // for(int i=1;i<=h;i++){
        //     for(int j=1;j<=w;j++) cout<<grid[i][j]<<' ';
        //     cout<<'\n';
        // }
    }

    cout<<ans<<'\n';

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 26784 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 22 ms 20948 KB Output is correct
5 Correct 30 ms 3572 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 2496 KB Output is correct
11 Correct 5 ms 6188 KB Output is correct
12 Correct 35 ms 9932 KB Output is correct
13 Correct 30 ms 3612 KB Output is correct
14 Correct 31 ms 3548 KB Output is correct
15 Correct 210 ms 8428 KB Output is correct
16 Correct 179 ms 26796 KB Output is correct
17 Correct 215 ms 10088 KB Output is correct
18 Correct 28 ms 20948 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1313 ms 31420 KB Output is correct
2 Execution timed out 2083 ms 14456 KB Time limit exceeded
3 Execution timed out 2081 ms 32536 KB Time limit exceeded
4 Execution timed out 2085 ms 36220 KB Time limit exceeded
5 Execution timed out 2074 ms 24672 KB Time limit exceeded
6 Runtime error 1456 ms 1048576 KB Execution killed with signal 9
7 Correct 1343 ms 32476 KB Output is correct
8 Correct 1411 ms 31580 KB Output is correct
9 Correct 70 ms 2064 KB Output is correct
10 Correct 138 ms 852 KB Output is correct
11 Correct 566 ms 31668 KB Output is correct
12 Correct 969 ms 2792 KB Output is correct
13 Execution timed out 2071 ms 14724 KB Time limit exceeded
14 Execution timed out 2077 ms 10360 KB Time limit exceeded
15 Execution timed out 2084 ms 10368 KB Time limit exceeded
16 Execution timed out 2080 ms 7464 KB Time limit exceeded
17 Execution timed out 2057 ms 18788 KB Time limit exceeded
18 Execution timed out 2066 ms 17488 KB Time limit exceeded
19 Execution timed out 2073 ms 36304 KB Time limit exceeded
20 Execution timed out 2077 ms 15296 KB Time limit exceeded
21 Execution timed out 2079 ms 25416 KB Time limit exceeded
22 Execution timed out 2061 ms 24744 KB Time limit exceeded
23 Execution timed out 2053 ms 22152 KB Time limit exceeded
24 Execution timed out 2077 ms 25636 KB Time limit exceeded
25 Execution timed out 2071 ms 32724 KB Time limit exceeded
26 Runtime error 658 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1124 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1099 ms 1048576 KB Execution killed with signal 9
29 Runtime error 982 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1119 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2113 ms 338352 KB Time limit exceeded
32 Runtime error 1079 ms 1048576 KB Execution killed with signal 9