oj.uz

Submission #811138

# Submission time Handle Problem Language Result Execution time Memory
811138 2023-08-07T01:04:21 Z kebine 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 265 ms 26836 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 26 ms 21000 KB Output is correct
5 Correct 31 ms 3520 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 2 ms 1108 KB Output is correct
10 Correct 27 ms 2524 KB Output is correct
11 Correct 6 ms 6220 KB Output is correct
12 Correct 42 ms 9800 KB Output is correct
13 Correct 33 ms 3680 KB Output is correct
14 Correct 36 ms 3624 KB Output is correct
15 Correct 301 ms 8720 KB Output is correct
16 Correct 235 ms 27064 KB Output is correct
17 Correct 260 ms 10296 KB Output is correct
18 Correct 26 ms 21004 KB Output is correct

Subtask #2
15.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 31472 KB Output is correct
2 Execution timed out 2076 ms 14380 KB Time limit exceeded
3 Execution timed out 2067 ms 32460 KB Time limit exceeded
4 Execution timed out 2068 ms 34860 KB Time limit exceeded
5 Execution timed out 2075 ms 24360 KB Time limit exceeded
6 Runtime error 1436 ms 1048576 KB Execution killed with signal 9
7 Correct 1454 ms 32332 KB Output is correct
8 Correct 1713 ms 31420 KB Output is correct
9 Correct 71 ms 2004 KB Output is correct
10 Correct 138 ms 912 KB Output is correct
11 Correct 636 ms 31488 KB Output is correct
12 Correct 1029 ms 2644 KB Output is correct
13 Execution timed out 2052 ms 14536 KB Time limit exceeded
14 Execution timed out 2060 ms 10088 KB Time limit exceeded
15 Execution timed out 2075 ms 9784 KB Time limit exceeded
16 Execution timed out 2086 ms 7196 KB Time limit exceeded
17 Execution timed out 2062 ms 18520 KB Time limit exceeded
18 Execution timed out 2079 ms 17144 KB Time limit exceeded
19 Execution timed out 2029 ms 35420 KB Time limit exceeded
20 Execution timed out 2056 ms 14968 KB Time limit exceeded
21 Execution timed out 2096 ms 25268 KB Time limit exceeded
22 Execution timed out 2077 ms 24432 KB Time limit exceeded
23 Execution timed out 2069 ms 21784 KB Time limit exceeded
24 Execution timed out 2077 ms 25388 KB Time limit exceeded
25 Execution timed out 2081 ms 32464 KB Time limit exceeded
26 Runtime error 667 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1045 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1078 ms 1048576 KB Execution killed with signal 9
29 Runtime error 990 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1227 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2108 ms 337352 KB Time limit exceeded
32 Runtime error 680 ms 1048576 KB Execution killed with signal 9