oj.uz

Submission #811328

# Submission time Handle Problem Language Result Execution time Memory
811328 2023-08-07T04:07:20 Z makanhulia 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 189 ms 26952 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 27 ms 20948 KB Output is correct
5 Correct 31 ms 3516 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 2504 KB Output is correct
11 Correct 5 ms 6192 KB Output is correct
12 Correct 39 ms 9924 KB Output is correct
13 Correct 36 ms 3540 KB Output is correct
14 Correct 40 ms 3588 KB Output is correct
15 Correct 217 ms 8544 KB Output is correct
16 Correct 213 ms 26744 KB Output is correct
17 Correct 232 ms 10048 KB Output is correct
18 Correct 24 ms 20912 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1212 ms 31404 KB Output is correct
2 Execution timed out 2059 ms 14468 KB Time limit exceeded
3 Execution timed out 2051 ms 32640 KB Time limit exceeded
4 Execution timed out 2080 ms 35740 KB Time limit exceeded
5 Execution timed out 2011 ms 24488 KB Time limit exceeded
6 Runtime error 1130 ms 1048576 KB Execution killed with signal 9
7 Correct 1286 ms 32332 KB Output is correct
8 Correct 1360 ms 31420 KB Output is correct
9 Correct 71 ms 2060 KB Output is correct
10 Correct 148 ms 856 KB Output is correct
11 Correct 525 ms 31536 KB Output is correct
12 Correct 976 ms 2732 KB Output is correct
13 Execution timed out 2067 ms 14488 KB Time limit exceeded
14 Execution timed out 2057 ms 10336 KB Time limit exceeded
15 Execution timed out 2083 ms 10136 KB Time limit exceeded
16 Execution timed out 2068 ms 7220 KB Time limit exceeded
17 Execution timed out 2013 ms 18752 KB Time limit exceeded
18 Execution timed out 2072 ms 17448 KB Time limit exceeded
19 Execution timed out 2104 ms 35360 KB Time limit exceeded
20 Execution timed out 2009 ms 15172 KB Time limit exceeded
21 Execution timed out 2088 ms 25636 KB Time limit exceeded
22 Execution timed out 2027 ms 24712 KB Time limit exceeded
23 Execution timed out 2031 ms 22148 KB Time limit exceeded
24 Execution timed out 2047 ms 25900 KB Time limit exceeded
25 Execution timed out 2075 ms 33004 KB Time limit exceeded
26 Runtime error 798 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1078 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1014 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1055 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1312 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2035 ms 338480 KB Time limit exceeded
32 Runtime error 662 ms 1048576 KB Execution killed with signal 9