oj.uz

Submission #812155

# Submission time Handle Problem Language Result Execution time Memory
812155 2023-08-07T07:31:57 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 218 ms 26832 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 31 ms 20948 KB Output is correct
5 Correct 37 ms 3500 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 27 ms 2508 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 36 ms 9812 KB Output is correct
13 Correct 31 ms 3512 KB Output is correct
14 Correct 31 ms 3592 KB Output is correct
15 Correct 210 ms 8440 KB Output is correct
16 Correct 192 ms 26828 KB Output is correct
17 Correct 218 ms 10048 KB Output is correct
18 Correct 25 ms 20840 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1369 ms 31412 KB Output is correct
2 Execution timed out 2070 ms 14456 KB Time limit exceeded
3 Execution timed out 2066 ms 32556 KB Time limit exceeded
4 Execution timed out 2071 ms 35576 KB Time limit exceeded
5 Execution timed out 2072 ms 24492 KB Time limit exceeded
6 Runtime error 1014 ms 1048576 KB Execution killed with signal 9
7 Correct 1237 ms 32300 KB Output is correct
8 Correct 1382 ms 31340 KB Output is correct
9 Correct 84 ms 2004 KB Output is correct
10 Correct 154 ms 840 KB Output is correct
11 Correct 467 ms 31480 KB Output is correct
12 Correct 1122 ms 2612 KB Output is correct
13 Execution timed out 2054 ms 14436 KB Time limit exceeded
14 Execution timed out 2069 ms 10080 KB Time limit exceeded
15 Execution timed out 2084 ms 9816 KB Time limit exceeded
16 Execution timed out 2052 ms 7208 KB Time limit exceeded
17 Execution timed out 2069 ms 18472 KB Time limit exceeded
18 Execution timed out 2066 ms 17368 KB Time limit exceeded
19 Execution timed out 2063 ms 35632 KB Time limit exceeded
20 Execution timed out 2057 ms 15040 KB Time limit exceeded
21 Execution timed out 2065 ms 25244 KB Time limit exceeded
22 Execution timed out 2044 ms 24416 KB Time limit exceeded
23 Execution timed out 2060 ms 21680 KB Time limit exceeded
24 Execution timed out 2057 ms 25372 KB Time limit exceeded
25 Execution timed out 2067 ms 32496 KB Time limit exceeded
26 Runtime error 699 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1047 ms 1048576 KB Execution killed with signal 9
28 Runtime error 972 ms 1048576 KB Execution killed with signal 9
29 Runtime error 933 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1295 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2091 ms 348272 KB Time limit exceeded
32 Runtime error 699 ms 1048576 KB Execution killed with signal 9