oj.uz

Submission #813599

# Submission time Handle Problem Language Result Execution time Memory
813599 2023-08-08T00:00:40 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 188 ms 27064 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 25 ms 21024 KB Output is correct
5 Correct 30 ms 3588 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1188 KB Output is correct
10 Correct 33 ms 2568 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 35 ms 9912 KB Output is correct
13 Correct 31 ms 3680 KB Output is correct
14 Correct 31 ms 3612 KB Output is correct
15 Correct 219 ms 8856 KB Output is correct
16 Correct 186 ms 27024 KB Output is correct
17 Correct 219 ms 10316 KB Output is correct
18 Correct 24 ms 21076 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 31564 KB Output is correct
2 Execution timed out 2068 ms 15936 KB Time limit exceeded
3 Execution timed out 2013 ms 47636 KB Time limit exceeded
4 Execution timed out 2023 ms 39440 KB Time limit exceeded
5 Execution timed out 2048 ms 32860 KB Time limit exceeded
6 Runtime error 1250 ms 1048576 KB Execution killed with signal 9
7 Correct 1340 ms 32604 KB Output is correct
8 Correct 1623 ms 31452 KB Output is correct
9 Correct 72 ms 2000 KB Output is correct
10 Correct 138 ms 856 KB Output is correct
11 Correct 596 ms 31540 KB Output is correct
12 Correct 1014 ms 2864 KB Output is correct
13 Execution timed out 2067 ms 15892 KB Time limit exceeded
14 Execution timed out 2057 ms 10968 KB Time limit exceeded
15 Execution timed out 2075 ms 10744 KB Time limit exceeded
16 Execution timed out 2050 ms 7836 KB Time limit exceeded
17 Execution timed out 2049 ms 22660 KB Time limit exceeded
18 Execution timed out 2058 ms 21092 KB Time limit exceeded
19 Execution timed out 2055 ms 39096 KB Time limit exceeded
20 Execution timed out 2065 ms 18488 KB Time limit exceeded
21 Execution timed out 2068 ms 34380 KB Time limit exceeded
22 Execution timed out 2009 ms 33284 KB Time limit exceeded
23 Execution timed out 2054 ms 29384 KB Time limit exceeded
24 Execution timed out 2078 ms 34276 KB Time limit exceeded
25 Execution timed out 2079 ms 48180 KB Time limit exceeded
26 Runtime error 712 ms 1048576 KB Execution killed with signal 9
27 Runtime error 962 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1008 ms 1048576 KB Execution killed with signal 9
29 Runtime error 977 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1115 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2086 ms 347340 KB Time limit exceeded
32 Runtime error 669 ms 1048576 KB Execution killed with signal 9